8

我已经用 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

上面返回预期结果。

4

3 回答 3

5

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，而不仅仅是一个。

于 2012-02-12T13:04:33.377 回答
3

您的工作版本的一些改进：

import Data.List
import Data.Function(on)

ks = knapsack []

knapsack :: [(Int, Int)] -> [(Int, Int)] -> Int -> [(Int, Int)]
knapsack xs [] _   = xs
knapsack xs ys max =
    foldr (maxOf) [] (xs: [knapsack (y:xs) (delete y ys) max
                           | y <- ys, weightOf(y:xs) <= max ] ) where
                             weightOf = sum . map snd

maxOf :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
maxOf a b = maximumBy (compare `on` valueOf) [a,b] where
            valueOf = sum . map fst
于 2012-02-12T17:15:01.397 回答
2

我可以建议使用动态编程方法吗？这种解决 0-1 背包问题的方法几乎慢得令人痛苦，至少当变量的数量大于 20 左右时是这样。虽然它很简单，但效率太低了。这是我的镜头：

import Array

-- creates the dynamic programming table as an array
dynProgTable (var,cap) = a where
    a = array ((0,0),(length var,cap)) [ ((i,j), best i j)
                       | i <- [0..length var] , j <- [0..cap] ] where
        best 0 _ = 0
        best _ 0 = 0
        best i j
            | snd (var !! (i-1)) > j = a!decline
            | otherwise          = maximum [a!decline,value+a!accept]
                where decline = (i-1,j)
                      accept  = (i-1,j - snd (var !! (i-1)))
                      value   = fst (var !! (i-1))

--Backtracks the solution from the dynamic programming table
--Output on the form [Int] where i'th element equals 1 if
--i'th variable was accepted, 0 otherwise.
solve (var,cap) =
    let j = cap
        i = length var
        table = dynProgTable (var,cap)
        step _ 0 _ = []
        step a k 0 = step table (k-1) 0 ++ [0]
        step a k l
            | a!(k,l) == a!(k-1,l) = step a (k-1) l ++ [0]
            | otherwise            = step a (k-1) (l - snd (var !! (k-1))) ++ [1]
    in step table i j

在输入 (var,cap) 中，var 是 2 元组 (c,w) 形式的变量列表，其中 c 是成本，w 是权重。cap 是最大重量限额。

我确信上面的代码可以被清理以使其更具可读性和明显性，但这就是我的结果:) 上面 Landei 的代码片段很短，我的计算机需要很长时间来计算只有 20 个变量的实例。上面的动态规划方法给了我一个更快的 1000 个变量的解决方案。

如果你不了解动态编程，你应该看看这个链接：关于动态编程的讲座幻灯片，它对我帮助很大。

有关数组的介绍，请查看数组教程。

于 2012-03-13T11:42:10.630 回答