剧透:我正在研究http://www.spoj.pl/problems/KNAPSACK/所以如果你不想为你破坏可能的解决方案,请不要偷看。
样板:
import Data.Sequence (index, fromList)
import Data.MemoCombinators (memo2, integral)
main = interact knapsackStr
knapsackStr :: String -> String
knapsackStr str = show $ knapsack items capacity numItems
where [capacity, numItems] = map read . words $ head ls
ls = lines str
items = map (makeItem . words) $ take numItems $ tail ls
一些设置舞台的类型和助手:
type Item = (Weight, Value)
type Weight = Int
type Value = Int
weight :: Item -> Weight
weight = fst
value :: Item -> Value
value = snd
makeItem :: [String] -> Item
makeItem [w, v] = (read w, read v)
主要功能:
knapsack :: [Item] -> Weight -> Int -> Value
knapsack itemsList = go
where go = memo2 integral integral knapsack'
items = fromList $ (0,0):itemsList
knapsack' 0 _ = 0
knapsack' _ 0 = 0
knapsack' w i | wi > w = exclude
| otherwise = max exclude include
where wi = weight item
vi = value item
item = items `index` i
exclude = go w (i-1)
include = go (w-wi) (i-1) + vi
这段代码有效;我尝试插入 SPOJ 示例测试用例,它会产生正确的结果。但是当我将这个解决方案提交给 SPOJ(而不是导入 Luke Palmer 的 MemoCombinators,我只是将必要的部分复制并粘贴到提交的源中)时,它超过了时间限制。=/
我不明白为什么;我之前问过一种执行 0-1 背包的有效方法,我相当确信这几乎是最快的:一个记忆函数,它只会递归地计算它绝对需要的子条目以产生正确的结果。我是否以某种方式搞砸了记忆?这段代码中是否有我遗漏的慢点?SPOJ 只是对 Haskell 有偏见吗?
我什至把{-# OPTIONS_GHC -O2 #-}
提交的顶部,但唉,它没有帮助。我尝试了一个类似的解决方案,它使用Sequence
s 的 2D 数组,但它也因为太慢而被拒绝。