2

さて、これは古い 0-1 ナップサックの問題ですが、取得できる合計最大価格を見つけた後、持ち運べるアイテムを見つける必要があります。ただし、次のテストケース（合計3項目）の場合

10 (max weight that I can carry)
5 3 (weight and value for each item)
5 2
6 5

ここでは、最大価格は 56です10(5+5)。どちらも同じ価格ですが、10 kg よりも 6 kg の商品の方が明らかに実現可能です。dp 行列からこれを計算する方法を教えてください。このテスト ケースの次のマトリックスを取得しました。

0 0 0 0 3 3 3 3 3 3 
0 0 0 0 3 3 3 3 3 5 
0 0 0 0 3 5 5 5 5 5

このアルゴリズムを使用すると、重量は 10 になりますが、最適は 6 kg です。

i=n, k=W(max weight)// n= total items

while i,k > 0

if dp[i,k] ≠ dp[i−1,k] then 
mark the ith item as in the knapsack
i = i−1, k = k-w(weight of ith item)

else
i = i−1
4

1 に答える 1

0

簡単な解決策は、さまざまなサイズのバッグでナップザック アルゴリズムを繰り返し実行し、元のバッグと同じ値が得られる最小のバッグを選択することです。

これは、重みに対してバイナリ検索[0,W]を使用して実行できます。したがって、ナップザック アルゴリズムを合計回実行し、最大値と可能な最小バッグ サイズを見つけるソリューションO(logW)の合計を取得します。O(nW*log(W))

二分探索を暗示する方法のアイデア:
元のバッグのサイズWを 、実行してknapsack(W,items)、 を取得するとしvalueます。knapsack(W/2,items)それでも が返されるかどうかを確認しますvalue。範囲内で検索します(0,W/2]。そうでない場合は、(W/2,W]を返す最小のバッグ サイズが見つかるまで range を検索しますvalue。

于 2012-06-07T08:59:27.983 に答える