01背包基础详解【转】_Find'Space_百度空间

测试数据：
10,3
3,4
4,5
5,6

1 2 3 4 5 6

//伪代码 for i=1 to n    for v=0 to w[i]-1          c[i,v]=c[i-1,v];//更新背包    for v=w[i] to V         c[i,v]=max{c[i-1,v],c[i-1,v-w[i]]+d[i]}

c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.w[i]是第i件物品的费用，d[i]是第i件物品的价值

这个最大价值是怎么得来的呢?

从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放4.

假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为4的时候，则最佳方案为自己的价值5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排c3的最佳方案是4.所以。总的最佳方案是5+4为9.

这样.一排一排推下去。

最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)

从以上最大价值的构造过程中可以看出。

Read full article from 01背包基础详解【转】_Find'Space_百度空间