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

动态规划,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]已经...
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
1,人们染上烟瘾,最终因吸烟使自己丧命.
最新试题
热门考点

超级试练试题库

© 2017-2019 超级试练试题库,All Rights Reserved.