相关疑难解决方法(0)

我在Haskell中编写了0-1背包问题.到目前为止,我对于懒惰和普遍性水平感到自豪.

我首先提供了创建和处理惰性2d矩阵的函数.

mkList f = map f [0..]
mkTable f = mkList (\i -> mkList (\j -> f i j))

tableIndex table i j = table !! i !! j

然后我为一个给定的背包问题制作一个特定的表格

knapsackTable = mkTable f
    where f 0 _ = 0
          f _ 0 = 0
          f i j | ws!!i > j = leaveI
                | otherwise = max takeI leaveI
              where takeI  = tableIndex knapsackTable (i-1) (j-(ws!!i)) + vs!!i
                    leaveI = tableIndex knapsackTable (i-1) j

-- weight …