5.10 Dynamic Programming: The Knapsack Problem - Introduction to Algorithms by Udi Manber

knapsack.hs

import Data.Array

knapsack :: [Int] -> Int -> Bool
knapsack xs cap = table!(cap, n)
  where
    n = length xs
    ks = listArray (1, n) xs
    table = array ((0,0), (cap, n)) $
      [((k, 0), k == 0) | k <- [0..cap]] ++
      [((k, i), ans k i) | k <- [0..cap], i <- [1..n]]
    ans k i = (k - ks!i >= 0 && table!(k - ks!i, i-1)) || table!(k, i-1)
 
weights = [2, 3, 5, 6]
capacity = 11

main :: IO()
main = do
  print $ knapsack weights capacity