0

宿題用に wiki のナップザック擬似コードを変更して、ナップザックで正確な重量 W を達成できるかどうかをチェックする必要があります。アイテムの数は無制限で、値は重要ではありません。j>-W[j] の下に while ループを追加して、同じアイテムがいくつ収まるかを確認することを考えています。それはうまくいきますか？

ありがとう

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for w from 0 to W do
  m[0, w] := 0
end for 
for i from 1 to n do
  for j from 0 to W do
    if j >= w[i] then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
    else
      m[i, j] := m[i-1, j]
    end if
  end for
end for
4

1 に答える 1

0

このwiki記事を参照している場合、私が何も見逃していない場合

変更されたバージョンでは、values配列は配列と同じになりますw。を計算m[n,W]したら、 と等しいかどうかを確認するだけWです。

編集:アイテムの数に制限がない場合は、Unbounded Knapsack Problemを扱っています。これは別の問題であり、同じ記事でそれを解決するための動的プログラミングの実装が示されています。

于 2013-11-15T08:03:54.207 に答える