首先要明确这张表是至底向上,从左到右生成的.
为了叙述方便,用e2单元格表示e行2列的单元格,这个单元格的意义是用来表示只有物品e时,有个承重为2的背包,那么这个背包的最大价值是0,因为e物品的重量是4,背包装不了.
对于d2单元格,表示只有物品e,d时承重为2的背包所能装入的最大价值,仍然是0,因为物品ed都不是这个背包能装的.
同理,c2=0,b2=3a2=6.
对于承重为8的背包,a8=15是怎么得出的呢?
根据01背包的状态转换方程,需要考察两个值,
一个是f[i-1j]对于这个例子来说就是b8的值9,另一个是f[i-1j-Wi]+Pi;
在这里,
f[i-1j-Wi]就是指单元格b6值为9,Pi指的是a物品的价值,即6
for(i=1;i<=m;i++)
for(j=t;j>=w[i];j--)