给定一个物品集合s={1,2,.....,n},物品i具有重量wi和价值vi。背包能承受能承受的最大载重量不超过W。背包问题就是找到一个物品子集s‘属于s,使得maxEwi<=W。所谓01背包就是物品要么整个地选取,要么不取。 首先我们先要肯定一件事,假设子问题(i,w)的最优装载中含有物品i,则其中的子问题(i-1,w-wi)的装载方案也一定是最优的。 证明:(反证法)假设子问题(i-1,w-wi)的装载方案p不是最优的,则有一个更优的装载方案p',将p'替换p然后在加上物品i将会比原来的最优装载价值最大,与假设矛盾。 现设定一个数组v[i,w](i代表第几个物品,w代表i物体的重量)表示将物品1到物品i的物品装入载重量为w的背包中所能获得的最大价值,即子问题(i,w)的最大价值 (1)对于物品i能够装进背包,则子问题(i,w)的最优解取决于物品i是否放进去 ①如果物品i不放进去,则有v[i,w]=v[i-1,w]。就是说i不放进去,那么容量为i的背包的价值==容量为i-1的背包的价值 ②若将物品i放进去,则有v[i,w]=v[i-1,w-wi]+vi。若i放进去,那么容量为i的背包的价值==容量为i-1的背包的价值加上第i个物品的价值 解析:相信大多数人都想不明白这句话的意思,若物品i能够放进去,那么一定是放进去后这个背包的价值肯定大于没放进去的价值大,这是错误的,假设有三个物品(1,1) (2,3)(2,2)【(物品重量,价值)】,现我们规定背包总重量限制于3,相信大家一眼就可以看出来,物品13的结合的价值没有物品12结合的价值大,自然3不放的总价 值大于2放的总价值,12放进去后此时背包容量已满,但倘若物品3放进去,那么背包为了能够容纳3,它必将2剔除,所以说3不放的价值大于放的价值。 现在为大家推一便算法,就明白了。 前提大家要先明确一件事,01背包算法精髓就是扫,假设背包容量为w,物品个数为n,那么可以假定的认为一个二维数组,行为第几个物品,第一行为第一个物品,第二行为第二个 物品,第n行为第n个物品。列为容量的多少,第一列是容量为1的背包,第二列是容量为2的背包,第三列为3,第n列为n。
给一组数据,物品号 wi vi 1 2 12 2 1 10 3 3 20 4 2 15
背包算法如下的表格所示 w i 0 1 2 3 4 5 1 0 12 12 12 12 2 10 12 22 22 22 3 10 10 22 30 32 4 10 15 25 30 37
解析:第1个[2,12]物品,背包容量为1时,2>1它进不了背包,背包容量为2时,进入背包,所以背包容量最大价值为12;背包容量为3,4,5时都可以进入背包,价值均为12。 第2个[1,10]物品,背包容量为1时,1==1进入背包;背包容量为2时,1<2则它可以选择进入或不进入,若进入c[2-`1][2-1]=10所以2号进入背包后的价值小于不进入背包的价值; 背包容量为3,4,5时背包都能够装满物品1,2所以1,2都放进去,容量为3,4,5的背包价值为22 第3个[3,20]物品,背包容量为1,2时,3>1,3>2,12都放不进去,背包容量为3时,进入后的价值20(会剔除1,2物品)<不进入的价值(22)所以3不进入;背包容量为4时,进入 的价值(剔除1号物品,还剩2号物品价值10)30>不进入的价值22,所以进入;背包容量为5时,进入的价值(剔除1号物品,剩余2号物品)32>不进入,所以进入 。 。
#include<stdio.h>
#include<string.h>
int c[10][100];/*对应每种情况的最大价值*/
int knapsack(int m,int n)//n是物品的个数,m是价值的限制
{
int i,j,w[10],p[10];
for(i=1;i<n+1;i++)
scanf("%d%d",&w[i],&p[i]);
memset(c,0,sizeof(c));
for(i=1;i<n+1;i++)//就下面的这两个循环和下面这个二维数组不明白!!
for(j=1;j<m+1;j++)
{
if(w[i]<=j) /*如果当前物品的容量小于背包容量*/
{
if(p[i]+c[i-1][j-w[i]]>c[i-1][j])//i-1个背包的价值加上第i个物品的价值是否大于不放的价值
/*如果本物品的价值加上背包剩下的空间能放的物品的价值*/
/*大于上一次选择的最佳方案则更新c[i][j]*/
c[i][j]=p[i]+c[i-1][j-w[i]];
else
c[i][j]=c[i-1][j];
}
else c[i][j]=c[i-1][j];
}
return(c[n][m]);
}
int main()
{
int m,n;int i,j;
scanf("%d%d",&n,&m);
printf("Input each one:\n");
printf("%d",knapsack(m,n));
printf("\n");/*下面是测试这个数组,可删除*/
for(i=0;i<5;i++)
for(j=0;j<6;j++)
{
printf("%d ",c[i][j]);
if(j==5)printf("\n");
}
return 0;
}
for (i=1;i<=n;i++)
{
for(j=v;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+p[i]);
}
}