动态规划,0-1背包问题
问题描述：
动态规划,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 这个循环到底是怎么回事?请大牛们帮我讲解一下.
不要发代码啊.只要讲解一下就行.我不理解这个循环的运行.
答
相当于一个滚动数组的处理for i=1..n bound=max{V-sum{w[i..n]},c[i]} for v=V..boundf[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]已经...