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

我不是在寻找有关如何清理代码的提示,只是为了让它正常工作.据我所知,它应该做以下事情:

• 对于每个元组选项(以y为单位)
  • 如果当前元组(y)的权重和运行总数(xs)的总和小于容量
  • 使用可用的元组(以y为单位)减去当前元组,得到包含当前元组和当前总数(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

返回上面的预期结果.

Answer 1

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

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

另一种方法是切换箱子的顺序，并向第一个箱子添加一个防护，表明该箱子ys必须至少包含一个不会使您超过总重量的元素（并调整另一个箱子，使其不需要ys为空） 。

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