我已经用 Scala 中的每个项目写了一个有界背包问题的答案,并尝试将其转换为 Haskell,结果如下:
knapsack :: [ ( Int, Int ) ] -> [ ( Int, Int ) ] -> Int -> [ ( Int, Int ) ]
knapsack xs [] _ = xs
knapsack xs ys max =
foldr (maxOf) [ ] [ knapsack ( y : xs ) ( filter (y /=) ys ) max | y <- ys
, weightOf( y : xs ) <= max ]
maxOf :: [ ( Int, Int ) ] -> [ ( Int, Int ) ] -> [ ( Int, Int ) ]
maxOf a b = if valueOf a > valueOf b then a else b
valueOf :: [ ( Int, Int ) ] -> Int
valueOf [ ] = 0
valueOf ( x : xs ) = fst x + valueOf xs
weightOf :: [ ( Int, Int ) ] -> Int
weightOf [ ] = 0
weightOf ( x : xs ) = snd x + weightOf xs
我不是在寻找关于如何清理代码的提示,只是为了让它工作。据我所知,它应该执行以下操作:
- 对于每个元组选项(在 ys 中)
- 如果当前元组 (y) 和运行总和 (xs) 组合的权重小于容量
- 使用可用的元组(以 ys 为单位)减去当前元组,得到包含当前元组和当前总数 (xs) 的最佳背包
- 最后,获取这些结果中最有价值的并返回
*编辑:*对不起,忘了说什么是错的......所以它编译好了,但它给出了错误的答案。对于以下输入,我期望什么以及它产生什么:
knapsack [] [(1,1),(2,2)] 5
Expect: [(1,1),(2,2)]
Produces: [(1,1),(2,2)]
knapsack [] [(1,1),(2,2),(3,3)] 5
Expect: [(2,2),(3,3)]
Produces: []
knapsack [] [(2,1),(3,2),(4,3),(6,4)] 5
Expect: [(2,1),(6,4)]
Produces: []
所以我想知道差异的原因可能是什么?
解决方案,感谢 sepp2k:
ks = knapsack []
knapsack :: [ ( Int, Int ) ] -> [ ( Int, Int ) ] -> Int -> [ ( Int, Int ) ]
knapsack xs [] _ = xs
knapsack xs ys max =
foldr (maxOf) [ ] ( xs : [ knapsack ( y : xs ) ( ys #- y ) max
| y <- ys, weightOf( y : xs ) <= max ] )
(#-) :: [ ( Int, Int ) ] -> ( Int, Int ) -> [ ( Int, Int ) ]
[ ] #- _ = [ ]
( x : xs ) #- y = if x == y then xs else x : ( xs #- y )
maxOf :: [ ( Int, Int ) ] -> [ ( Int, Int ) ] -> [ ( Int, Int ) ]
maxOf a b = if valueOf a > valueOf b then a else b
valueOf :: [ ( Int, Int ) ] -> Int
valueOf [ ] = 0
valueOf ( x : xs ) = fst x + valueOf xs
weightOf :: [ ( Int, Int ) ] -> Int
weightOf [ ] = 0
weightOf ( x : xs ) = snd x + weightOf xs
上面返回预期结果。