首先要明确这张表是至底向上，从左到右生成的。
为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。
对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。
同理，c2=0，b2=3,a2=6。
对于承重为8的背包，a8=15,是怎么得出的呢？
根据01背包的状态转换方程，需要考察两个值，
一个是f[i-1,j],对于这个例子来说就是b8的值9，另一个是f[i-1,j-Wi]+Pi；
在这里，
f[i-1,j]表示我有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值
f[i-1,j-Wi]表示我有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值
f[i-1,j-Wi]就是指单元格b6,值为9，Pi指的是a物品的价值，即6
由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a应该放入承重为8的背包
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<stdio.h> #include<conio.h> #include<string.h> int f[1010],w[1010],v[1010];//f记录不同承重量背包的总价值，w记录不同物品的重量，v记录不同物品的价值 int max(int x,int y){//返回x,y的最大值 if(x>y) return x; return y; } int main() { int t,m,i,j; memset(f,0,sizeof(f)); //总价值初始化为0 printf("输入背包承重量t、物品的数目m\n"); scanf("%d %d",&t,&m); //输入背包承重量t、物品的数目m for(i=1;i<=m;i++) { printf("%d:",i); scanf("%d %d",&w[i],&v[i]); //输入m组物品的重量w[i]和价值v[i] } for(i=1;i<=m;i++)//尝试放置每一个物品 { for(j=t;j>=w[i];j--) { f[j]=max(f[j-w[i]]+v[i],f[j]); //在放入第i个物品前后，检验不同j承重量背包的总价值， //如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变 } } printf("%d",f[t]); //输出承重量为t的背包的总价值 printf("\n"); getch(); return 0; } |
