0

0~1のナップザック問題は、

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

c[i] は i 番目の商品のコストを意味し、w[i] は i 番目の商品の価値を意味します。

そして、特にVが大きい場合、時間の複雑さが最適化される可能性があると述べた1つのドキュメントを読みました。以下のように

 i=1...N

 v=V...0

に変更できます 

 i=1...n        

bound=max{V-sum{w[i..n]},c[i]}        

 v=V...bound

どういう意味ですか?V(バッグの最大値)からw[i](商品の価値)の合計を引く方法は?

本当に混乱していますか、それともこのドキュメントで何か問題がありますか?

4

1 に答える 1

1

誰の複雑さを最適化しているかは言いませんでした。動的計画法を使用していますか？もしそうなら、これf[i][v]は v の小さい値を計算する必要がないことを意味するかもしれません。なぜなら、それらの値は最適値を見つけるために必要ないからです。

i + 1からまでの商品をすべてnナップザックに入れても、残りの容量があるので、それより小さい容量の副問題(商品 に限る)V - sum{c[i+1..n]}を解く必要はありません。i1..i

より正式な回答が必要な場合は、問題と使用されているアルゴリズムを詳細に説明してください。

于 2013-01-10T02:32:14.983 に答える