如何理解約0〜1揹包減少時間複雜

Question

至於0〜1揹包問題，

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

C [1]表示第i個商品的成本， 瓦特[I]表示的值ith貨物。

和我讀到一個文檔，裏面說的時間複雜度可以優化，尤其是當V低於

i=1...N 

v=V...0 

larger.as可改爲

i=1...n   

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

v=V...bound 

這是什麼意思？ V（袋子的最大值）減去W [i]的總和（貨物的價值）？

真的很迷惑，或者這個文檔有問題嗎？

Answer 1

你沒有說你正在優化的是誰的複雜性。你在使用動態編程嗎？如果是這樣，這可能意味着你不需要爲小的v值計算f[i][v]，因爲你不需要這些值來找到最佳值。

即使你把所有的商品從i + 1到n的揹包，你仍然有V - sum{c[i+1..n]}左右的容量，所以你並不需要求解子i用容量小於（僅限於貨物1..i） 。

如果您需要更正式的答案，請詳細描述問題以及正在使用的算法。