1、给定一个物品集合给定一个物品集合s1,2,3,n,物品,物品i的的重量是重量是wi,其其价值是价值是vi,背包的,背包的容量为容量为W,即最大载重量不超过,即最大载重量不超过W。在限定的总重量。在限定的总重量W内,我们如何选择物品,才能使得物品内,我们如何选择物品,才能使得物品的的总价值最大总价值最大。l 如果物品不能被分割,即物品如果物品不能被分割,即物品i要么整个地选取,要么不选取;要么整个地选取,要么不选取;l 不能将物品不能将物品i装入背包多次,也不能只装入部分物品装入背包多次,也不能只装入部分物品i,则该问题称为,则该问题称为01背包问题背包问题。l 如果物品可以拆分,则问题称为背包
2、问题,适合使用如果物品可以拆分,则问题称为背包问题,适合使用贪心算法贪心算法。1假设假设xi表示物品表示物品i装入背包的情况,装入背包的情况,xi0,1。l 当当xi0时,表示物品没有装入背包时,表示物品没有装入背包;l 当当xi1时时,表示把物品装入背包,表示把物品装入背包。约束方程约束方程:W目标函数目标函数:因此问题就归结为找到一个满足上述约束方程因此问题就归结为找到一个满足上述约束方程,并并使使的解向量:的解向量:Xx1,x2,xn,2niiixw1niiixv1max01背包背包问题具有最优子结构性质,设所给问题具有最优子结构性质,设所给01背包背包问题的子问题:问题的子问题:ikn
3、的最优值为的最优值为p(i,j)。l 是是背包容量为背包容量为j,可选物品为,可选物品为i,i1,n时时0-1背包背包问题的最优值问题的最优值。31 2 3 i i+1 np(i,j),背包容量,背包容量jp(i+1,j):不装入物品:不装入物品i,背包容量,背包容量jp(i+1,j-wi)+vi:装入物品:装入物品i,背包容量,背包容量j-winikkknikkkjxwxvmax 10,kx则建立计算则建立计算p(i,j)的递归式如下:的递归式如下:41 2 3 i i+1 np(i,j),背包容量,背包容量jp(i+1,j):不装入物品:不装入物品i,背包容量,背包容量jp(i+1,j-w
4、i)+vi:装入物品:装入物品i,背包容量,背包容量j-wiiiiiwj0 jipwj vwjipjipjip)1()1()1(max()(,nnnwj0 wj vjnp0)(,则建立计算则建立计算p(i,j)的递归式如下:的递归式如下:5iiiiwj0 jipwj vwjipjipjip)1()1()1(max()(,nnnwj0 wj vjnp0)(,W=5 1234重量重量w2132价值价值v12102015n|j012345100000372010152530353001520203540015151515背包的容量为背包的容量为5 5m21=max(m31,m30+10)=10;m2
5、2=max(m32,m31+10)=15;m23=max(m33,m32+10)=25;m24=max(m34,m33+10)=30;m25=max(m35,m34+10)=35;m15=max(m25,m23+12)=37;#define NUM 50/物品数量的上限物品数量的上限#define CAP 1500/背包容量的上限背包容量的上限int wNUM;/物品的重量物品的重量int vNUM;/物品的价值物品的价值int pNUMCAP;/用于递归的数组用于递归的数组/形参形参c是背包的容量是背包的容量W,n是物品的数量是物品的数量void knapsack(int c,int n)/
6、计算递推边界计算递推边界int jMax=min(wn-1,c);/分界点分界点for(int i=n-1;i1;i-)/计算递推式计算递推式 jMax=min(wi-1,c);for(int j=0;j=jMax;j+)pij=pi+1j;for(int j=wi;j=w1)p1c=max(p1c,p2c-w1+v1);6nnnwj0 wj vjnp0)(,iiiiwj0 jipwj vwjipjipjip)1()1()1(max()(,主要是计算数组主要是计算数组p的时间,的时间,其时间复杂度为其时间复杂度为O(nW)void traceback(int c,int n,int x)for(int i=1;in;i+)if(pic=pi+1c)xi=0;else xi=1;c-=wi;xn=(pnc)?1:0;7n|j012345100000372010152530353001520203540015151515W=5 1234重量重量w2132价值价值v12102015最优解最优解x1101