哈斯克爾揹包

Question

我寫的答案，有界揹包問題與Scala中的每個項目中的一個，並試圖調換其結果如下哈斯克爾：

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）相結合的重量小於容量
  • 獲得包含當前元組和當前總（XS）的最佳揹包，使用可用的元組（在YS）少當前多元組
• 最後，獲得最有價值這些結果和回報它

* 編輯：*對不起，忘了說出了什麼問題......所以編譯好了，但它給出了錯誤的答案。對於下面的投入，我期望與它產生：

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，而不僅僅是一個。

Answer 2

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

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 

Answer 3

我可以建議使用動態規劃方法？這種解決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，帽），VAR是在2元組形式的變量列表（C，W），其中c是成本和w是重量。帽子是最大重量限額。

我確信上面的代碼可以清理出來，使它更易讀，更明顯，但這就是它的原因:)上面Landei的代碼段很短，我的電腦只用了很長時間的計算實例20個變量。上面的動態編程方法爲我提供了1000個變量的解決方案。

如果你不瞭解動態編程，你應該看看這個鏈接：Lecture slides on dynamic programming，它幫了我很多。

有關陣列的介紹，請查看Array tutorial。