關於01背包問題九講的優化?

01-08

我想請問一下，中間的部分， bound=max{V-sum{weight[i..n]},weight[i]}，為什麼是sum{weight[i..n]}，而不是sum{weight[i+1..n]}，不是下面還要再減一次嗎？

大概是這麼想的吧。

因為解是最後一個值，即f[v]，而對於f[v]和最後一件要放入的物品n來說，只需要知道f[v-cn]是多少就行；於是，同理，對 $f[v-c_{n}]$ 和物品n-1來說，需要的是 $f[v-c_{n}-c_{n-1} ]$ 。

於是，到物品i，也就是物品n-(n-i)，需要的就是 $f[v-{c_{n}- ... -c_{i}}]$ 。

然而，有的物品可能是不會放進去的而且f[-1]是不存在的，於是，max{V-sum{c[i..n]},c[i]}。

就是不知道作者說的

這個優化之所以成立的原因請讀者自己思考。(提示:使用二維的轉移方程思
考較易。)

提示是不是這個意思。