haskell 背包

Question

我已经用 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)的最佳背包
• 最后，获取这些结果中最有值(value)的部分并将其返回

*编辑:* 抱歉，忘了说出了什么问题...所以它可以正常编译，但给出了错误的答案。对于以下输入，我期望什么以及它产生什么:

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

这会返回上面的预期结果。

Answer 1

您的第一个案例在 ys 时触发包含。所以对于knapsack [foo,bar] [] 42 ，你回来[foo, bar] ，这就是你想要的。但是，当 ys 时它不会触发。除了会让你超过最大重量的元素之外，不包含任何内容，即 knapsack [(x, 20), (y,20)] [(bla, 5)]将返回[]从而丢弃之前的结果。由于这不是您想要的，您应该调整您的情况，以便仅当 ys 中至少有一个元素时才会触发第二种情况。这低于最大重量。

做到这一点的一种方法是在递归时丢弃任何使您超过最大权重的元素，这样这种情况就不会发生。

另一种方法是切换案例的顺序，并向第一个案例添加一个防护，表示 ys必须包含至少一个不会使您超过总重量的元素(并调整其他情况以不要求 ys 为空)。

PS:与您的代码无关的另一个问题是它忽略重复项。 IE。如果您在列表中使用它 [(2,2), (2,2)]它将表现得好像列表只是 [(2,2)]因为filter (y /=) ys将抛出所有出现的 y ，不仅仅是一个。