动态规划,0-1背包问题在背包问题九讲中p01 01背包中有这样一段话：一个常数优化前面的伪代码中有 for v=V..1,可以将这个循环的下限进行改进.由于只需要最后f[v]的值,倒推前一个物品,其实只

动态规划,0-1背包问题在背包问题九讲中p01 01背包中有这样一段话：一个常数优化前面的伪代码中有 for v=V..1,可以将这个循环的下限进行改进.由于只需要最后f[v]的值,倒推前一个物品,其实只
动态规划,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 这个循环到底是怎么回事?请大牛们帮我讲解一下.
不要发代码啊.只要讲解一下就行.我不理解这个循环的运行.

动态规划,0-1背包问题在背包问题九讲中p01 01背包中有这样一段话：一个常数优化前面的伪代码中有 for v=V..1,可以将这个循环的下限进行改进.由于只需要最后f[v]的值,倒推前一个物品,其实只
相当于一个滚动数组的处理
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;ic[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]);
}