大概看懂了0-1背包(动态规划)

动态规划最泛的思想就是从最小的问题开始,每一步的结果都保存下来,以后更大的结果就直接用小的结果来构造,这样就减少很大的计算量.

我们所要的就是那个最大的结果

?

?

?

?

在解决0-1背包问题中:

两个循环嵌套,一个循环容量(从1开始,步长为1),一个循环个数(从1开始,步长为1)

?

最佳方案存在一个二维数组里,?大小为?(最大容量?+?1)*(最大个数?+?1)

第一行和第一列为?0,作为起始条件.

?

?

如果??(本物体价值?+?出去本物体的剩余空间的最佳方案)?>?(上一次最佳方案)

???则?本次最佳方案?=?(本物体价值?+?出去本物体的剩余空间的最佳方案)

否则??本次最佳方案?=?上一次最佳方案

在这之前还要保证本物体的限制条件?

过几天再写个小程序实现,要写作业了.