Question

动态规划，0-1背包问题

在背包问题九讲中p01 01背包中有这样一段话：
一个常数优化
前面的伪代码中有 for v=V..1，可以将这个循环的下限进行改进。 由于只需要最后f[v]的值，倒推前一个物品，其实只要知道f[v-w[n]]即可。以此类推，对以第j个背包，其实只需要知道到f[v-sum{w[j..n]}]即可，即代码中的 for i=1..N for v=V..0 可以改成 for i=1..n bound=max{V-sum{w[i..n]},c[i]} for v=V..bound 这对于V比较大时是有用的。

for i=1..n bound=max{V-sum{w[i..n]},c[i]} for v=V..bound 这个循环到底是怎么回事？？？请大牛们帮我讲解一下。。。谢谢~
不要发代码啊。只要讲解一下就行。我不理解这个循环的运行。。。

Answer 1

相当于一个滚动数组的处理

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

f[i][j]=max{f[i-1][j-w[i]]+c[i],f[i-1][j]}
现在我们处理好了
f[i][0...V]
现在处理f[i+1][0...V]时...
我们发现f[i-1][0...V]已经没用了
可是还站着内存..所以只需要一维..在状态转移时滚动就行了

而f[i][j]只与f[i-1][j]和f[i-1][j-w[i]]有关
滚动就像
f[j]只与f[j]和f[j-w[i]]有关
而如果bound...V去循环
会提早改了某个j-w[i]
所以要V...bound去循环

sum[N]=c[N];
for(int i=N-1;i>=1;i--)
sum[i]=sum[i+1]+c[i];//预处理得到sum数组

for(int i=1;i<=N;i++)
{
low=((V-sum[i])>c[i])?(V-sum[i]):c[i];
for(int j=V;j>=low;j--)
f[j]=(f[j]>f[j-c[i]])?(f[j]):(f[j-c[i]]+w[i]);
}