大概看懂了0-1背包(动态规划)
动态规划最泛的思想就是从最小的问题开始,每一步的结果都保存下来,以后更大的结果就直接用小的结果来构造,这样就减少很大的计算量.
我们所要的就是那个最大的结果
?
?
?
?
在解决0-1背包问题中:
两个循环嵌套,一个循环容量(从1开始,步长为1),一个循环个数(从1开始,步长为1)
?
最佳方案存在一个二维数组里,?大小为?(最大容量?+?1)*(最大个数?+?1)
第一行和第一列为?0,作为起始条件.
?
?
如果??(本物体价值?+?出去本物体的剩余空间的最佳方案)?>?(上一次最佳方案)
???则?本次最佳方案?=?(本物体价值?+?出去本物体的剩余空间的最佳方案)
否则??本次最佳方案?=?上一次最佳方案
在这之前还要保证本物体的限制条件?
过几天再写个小程序实现,要写作业了.
