ナップサック問題

のためのテンプレ。

type Weight = Int
type Value = Int

table :: [(Weight, Value)] -> [Value]
table is = foldl nextLine (repeat 0) is
  where
  nextLine ps (wi,pi) = 0 : map memoCell [1..]
    where
--  for 0-1 knapsack problem
    memoCell w = if w<wi then ps!!w else max (ps!!w) (pi + ps!!(w-wi))
--  for unbounded knapsack problem
--    memoCell w = maximum $ zipWith (+) (map (pi*) [0..]) (map (ps!!) [w,w-wi..0])

knapsack :: [(Weight, Value)] -> Weight -> Value
knapsack is w = table is !! w

main = print $ knapsack [(1,1),(1,2),(2,2),(4,10),(12,4)] 15

参考：Knapsack problem - Wikipedia