8

Scala の各項目の 1 つを使用して境界付きナップザックの問題に対する回答を書き、次の結果で 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これはあなたが望むものではないので、最大重量を下回る要素が少なくとも 1 つある場合にのみ 2 番目のケースが起動するように、ケースを調整する必要があります。

これを行う 1 つの方法は、再帰時に最大の重みを超える要素を破棄して、そのシナリオが発生しないようにすることです。

別の方法は、ケースの順序を切り替えて、最初のケースにガードを追加することysです。これには、合計重量を超えない要素が少なくとも 1 つ含まれている必要があります (そして、他のケースをys空にする必要がないように調整します)。 .

PS: コードのもう 1 つの無関係な問題は、重複を無視することです。つまり、リストで使用すると、リストが の 1 つだけでなく、すべての出現を破棄するという理由[(2,2), (2,2)]だけであるかのように動作します。[(2,2)]filter (y /=) ysy

于 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 に答える