首先要明确这张表是至底向上,从左到右生成的。 为了叙述方便,用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的背包 代码:
C++
#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;
}