6

有界ナップザック問題の場合、各アイテムの値がその重量と同じで、すべての重量が正の整数であると仮定すると、個々のアイテムの重量がアイテムの数 nと比較して小さい場合の最適化があるかどうか疑問に思っています。ナップザックの容量は、すべてのアイテムの重量の合計の半分ですか? たとえば、100k アイテムで、各アイテムの重みは [1, 10] に制限されます。

アルゴリズムは正確な解を与える必要があります。私は O(n*W) 時間と O(W) 空間 DP アルゴリズムを認識していますが、この場合、それを解決するためのより良い方法があるかもしれないと考えました。前もって感謝します。

これはアルゴリズムの課題によるもので、O(n*W) 時間のソリューションは機能的には正しいものでしたが、十分に高速ではありませんでした (必要なサイズよりも遅い)。そして、私はこの問題について何も見つけられないようです。入力はアイテムの重量のリストであり、必要な出力はナップザックに収まるアイテムの最大合計値です。

4

2 に答える 2

6

あなたが探している論文は、Pisinger 1999、「境界のある重みを持つナップサック問題の線形時間アルゴリズム」です。ただし、一部の変数の識別マークが pdf から失われているように見えるため、少し面倒です。

アイテムb (ブレーク アイテム)に到達するまで、任意の順序でアイテムをソリューションに追加します。これにより、 Wを超えます。アイテム1、2、... b-1はバランスのとれた詰め物を構成し、他のすべてのバランスのとれた詰め物は、一連の 2 つの操作によって到達できるものです。

  • バランスの取れた挿入とは、重量<= Wのバランスの取れたソリューションにbまたはそれ以上のアイテムを追加することです。
  • バランスの取れた削除とは、重みが> Wのバランスの取れたソリューションからbの前の項目を削除することです。

2 つのことは非常に簡単にわかります。1 つ目は、すべての平衡解がWの 10 単位の重量内にあること、2 つ目は、最適解は平衡解でなければならないことです。

動的計画法によって、初期解から最適解への道を見つけます。

  • b以降の各項目tについて、
  • W - 9 < w < W + 10となる各重みwについて、
  • bの前の最新のアイテムsを追跡します
  • sとtの間だけでアイテムを追加/削除することで到達できる重量wのバランスの取れた充填があるように

それを数回読んでください。途中のある時点で、最適なソリューションに到達することが保証されていることに注意してください (ただし、最後までわかりません)。wBreakをブレーク項目が追加される前の重みにすると、アルゴリズムは次のように初期化されます。

for (w = W-9, w <= W, w++) { s(b-1, w) = 0 }
for (w = W+1, w <= W+10, w++) { s(b-1, w) = 1 }

s(b, wBreak) = b - 1

s(b, wBreak)を除いて、これらはすべてデフォルトです。次に、肉に行きます。

for (t = b, t <= N, t++) 
{
    for (w = W-9, w <= W, w++) 
    {
        // Trying adding item t to the solutions with weight <= W 
        s(t, w + w_t) = max( s(t-1, w), s(t-1, w + w_t) )   
    }
    for (w = W+10, w > W, w--)
    {
        // Removing as many items as needed to get back to a balanced filling
        for (j = s(t, w) - 1, j >= s(t-1, w), j--) 
        {
            s(t, w - w_j) = max( s(t, w - w_j), j )
        }
    }
}

全体として、これにはO(N)時間がかかり、最適な塗りつぶしの重みは、Wに最も近く、それよりも大きくないwを持つ非自明なs(t,w)として識別できます。

これは、すべてのアイテムの重量の合計が 2W であるという事実を利用していないことに注意してください。それを使って簡略化を考えてみますが、W を満たすのに十分なアイテムがない場合の些細なエッジ ケースについて心配する必要がないように、質問設定者が追加した可能性があります。

于 2013-09-22T22:01:06.693 に答える
1

Pisinger の 1999 年の論文 Bounded Knapsack は http://www.diku.dk/~pisinger/94-27.ps にあり、実装されたコードは http://www.diku.dk/~pisinger/codes.html にあります。 bouknap.c

于 2015-05-08T16:54:23.183 に答える