Exemplo de programação dinâmica em Haskell

knapsack.hs

{- INPUT:
4 300
30 10
20 50
1 2
4 6
-}
{- OUTPUT:
900
-}
import Data.Array
import Control.Monad

solve items i_max m_max =  go i_max m_max
  where go 0 _ = 0
        go _ 0 = 0
        go i m = max a b
          where c_i = c $ items ! i
                p_i = p $ items ! i
                a = memo ! (i-1, m)
                b = if c_i <= m
                       then p_i + (memo ! (i, m - c_i))
                       else 0

        memo = listArray ((0,0), (i_max,m_max)) [go i m |
          i <- [0..i_max],
          m <- [0..m_max]]

data Item = Item { p :: Int, c :: Int }

readItem :: IO Item
readItem = do [p,c] <- map read .words <$> getLine
              return $ Item p c

main = do
  [n, m] <- map read . words <$> getLine
  items <- replicateM n readItem
  print $ solve (listArray (1, n) items) n m