给定一个物品集合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];//w是容量,p是价值
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]);

}

 

发表评论

电子邮件地址不会被公开。

Post Navigation