Haskellのナップザック

Question

私はスカラ座の各項目の一つで有界ナップザック問題への答えを書いて、下記の結果と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 

以上、期待される結果を返します。

Answer 1

ysが含まれていると、最初のケースが発生します。だからknapsack [foo,bar] [] 42の場合は、[foo, bar]に戻ります。ただし、最大重量を超える要素が含まれている場合、knapsack [(x, 20), (y,20)] [(bla, 5)]は[]を返すため、ysには何も含まれていないため、前の結果は破棄されません。これはあなたが望むものではないので、少なくとも1つの要素が最大重量よりも小さいysにある場合にのみ、2番目のケースが起動するようにケースを調整する必要があります。

これを実行する方法の1つは、繰り返し実行するときに最大の重みを超える要素を除外することです。そのシナリオは単純には起こりません。

もう1つの方法は、ケースの順序を変更し、ysに総重量を超えない少なくとも1つの要素が含まれている必要があるという最初のケースにガードを追加することです（そして、 ysを空にする必要があります）。

PS：コードに関連しない別の問題は、重複を無視することです。私。 のリストで使用すると、filter (y /=) ysは1つだけでなく、yのすべてのオカレンスをスローするため、リストがちょうど[(2,2)]のようになります。あなたの作業バージョンに

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を超えると、ほとんど痛みを伴いません。単純ですが、あまり効果がありません。ここでの私のショットです：入力（VAR、キャップ）で

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は、cは、コストとwがあるある2つのタプル（C、W）の形で変数のリストです重量。キャップは最大重量許容値です。

私は上記のコードを読みやすく分かりやすくするためにクリーンアップすることができると確信していますが、それは私のために判明しました:) Landeiのコードスニペットは短いですが、 20の変数。上記の動的プログラミング手法は、1000変数の解をより速く得ました。

ダイナミックプログラミングについて知らない場合は、Lecture slides on dynamic programmingのリンクをご覧ください。

アレイについては、Array tutorialをご覧ください。