0019算法笔记【动态规划】0-1背包问题

0019算法笔记——【动态规划】0-1背包问题1、问题描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c0,wi0,vi0,1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1},∋∑wixi≤c,且∑vixi达最大.即一个特殊的整数规划问题。2、最优性原理：设(y1,y2,…,yn)是(3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解:证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有∑vizi∑viyi(i=2,…,n)且w1y1+∑wizi=c因此v1y1+∑vizi(i=2,…,n)∑viyi,(i=1,…,n)说明(y1,z2,z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。3、递推关系：设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式:注:(3.4.3)式此时背包容量为j，可选择物品为i。此时在对xi作出决策之后,问题处于两种状态之一:(1)背包剩余容量是j,没产生任何效益；(2)剩余容量j-wi,效益值增长了vi；算法具体代码如下：[cpp]viewplaincopy1.//3d10-1动态规划背包问题2.#includestdafx.h3.#includeiostream4.usingnamespacestd;5.6.constintN=4;7.8.voidKnapsack(intv[],intw[],intc,intn,intm[][10]);9.voidTraceback(intm[][10],intw[],intc,intn,intx[]);10.11.intmain()12.{13.intc=8;14.intv[]={0,2,1,4,3},w[]={0,1,4,2,3};//下标从1开始15.intx[N+1];16.intm[10][10];17.18.cout待装物品重量分别为：endl;19.for(inti=1;i=N;i++)20.{21.coutw[i];22.}23.coutendl;24.25.cout待装物品价值分别为：endl;26.for(inti=1;i=N;i++)27.{28.coutv[i];29.}30.coutendl;31.32.Knapsack(v,w,c,N,m);33.34.cout背包能装的最大价值为：m[1][c]endl;35.36.Traceback(m,w,c,N,x);37.cout背包装下的物品编号为：endl;38.for(inti=1;i=N;i++)39.{40.if(x[i]==1)41.{42.couti;43.}44.}45.coutendl;46.47.return0;48.}49.50.voidKnapsack(intv[],intw[],intc,intn,intm[][10])51.{52.intjMax=min(w[n]-1,c);//背包剩余容量上限范围[0~w[n]-1]53.for(intj=0;j=jMax;j++)54.{55.m[n][j]=0;56.}57.58.for(intj=w[n];j=c;j++)//限制范围[w[n]~c]59.{60.m[n][j]=v[n];61.}62.63.for(inti=n-1;i1;i--)64.{65.jMax=min(w[i]-1,c);66.for(intj=0;j=jMax;j++)//背包不同剩余容量j=jMaxc67.{68.m[i][j]=m[i+1][j];//没产生任何效益69.}70.71.for(intj=w[i];j=c;j++)//背包不同剩余容量j-wic72.{73.m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//效益值增长vi74.}75.}76.m[1][c]=m[2][c];77.if(c=w[1])78.{79.m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);80.}81.}82.83.//x[]数组存储对应物品0-1向量,0不装入背包，1表示装入背包84.voidTraceback(intm[][10],intw[],intc,intn,intx[])85.{86.for(inti=1;in;i++)87.{88.if(m[i][c]==m[i+1][c])89.{90.x[i]=0;91.}92.else93.{94.x[i]=1;95.c-=w[i];96.}97.}98.x[n]=(m[n][c])?1:0;99.}算法执行过程对m[][]填表及Traceback回溯过程如图所示：从m(i，j)的递归式容易看出，算法Knapsack需要O(nc)计算时间;Traceback需O(n)计算时间；算法总体需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2^n时，算法需要Ω(n2^n)计算时间。4、算法的改进：由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1≤i≤n)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全部跳跃点唯一确定。如图所示。对每一个确定的i(1≤i≤n)，用一个表p[i]存储函数m(i，j)的全部跳跃点。表p[i]可依计算m(i，j)的递归式递归地由表p[i+1]计算，初始时p[n+1]={(0，0)}。一个例子：n=3，c=6，w={4，3，2}，v={5，2，1}。函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算得到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j)的跳跃点集p[i+1]与函数m(i+1，j-wi)+vi的跳跃点集q[i+1]的并集中。易知，(s,t)∈q[i+1]当且仅当wi=s=c且(s-wi,t-vi)∈p[i+1]。因此，容易由p[i+1]确定跳跃点集q[i+1]如下：q[i+1]=p[i+1]⊕(wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))∈p[i+1]}另一方面，设(a，b)和(c，d)是p[i+1]∪q[i+1]中的2个跳跃点，则当c=a且db时，(c，d)受控于(a，b)，从而(c，d)不是p[i]中的跳跃点。除受控跳跃点外，p[i+1]∪q[i+1]中的其他跳跃点均为p[i]中的跳跃点。由此可见，在递归地由表p[i+1]计算表p[i]时，可先由p[i+1]计算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳跃点得到表p[i]。例：n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。跳跃点的计算过程如下：初始时p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6]⊕(w5,v5)={(4,6)}。p[5]={(0,0),(4,6)}。q[5]=p[5]⊕(w4,v4)={(5,4),(9,10)}。从跳跃点集p[5]与q[5]的并集p[5]∪q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)}q[4]=p[4]⊕(6，5)={(6，5)，(10，11)}p[3]={(0，0)，(4，6)，(9，10)，(10，11)}q[3]=p[3]⊕(2，3)={(2，3)，(6，9)}p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}q[2]=p[2]⊕(2，6)={(2，6)，(4，9)，(6，12)，(8，15)}p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。具体代码实现如下：[cpp]viewplaincopy1.//3d10-2动态规划背包问题跳跃点优化2.#includestdafx.h3.#includeiostream4.usingnamespacestd;5.6.constintN=4;7.8.templateclassType9.intKnapsack(intn,Typec,Typev[],Typew[],int**p,intx[]);10.templateclassType11.voidTraceback(intn,Typew[],Typev[],Type**p,int*head,intx[]);12.13.intmain()14.{15.intc=8;16.intv[]={0,2,1,4,3},w[]={0,1,4,2,3};//下标从1开始17.intx[N+1];18.19.int**p=newint*[50];20.for(inti=0;i50;i++)21.{22.p[i]=newint[2];23.}24.25.cout待装物品重量分别为：endl;26.for(inti=1;i=N;i++)27.{28.coutw[i];29.}30.coutendl;31.32.cout待装物品价值分别为：endl;33.for(inti=1;i=N;i++)34.{35.coutv[i];36.}37.coutendl;38.39.cout背包能装的最大价值为：Knapsack(N,c,v,w,p,x)endl;40.41.cout背包装下的物品编号为：endl;42.for(inti=1;i=N;i++)43.{44.if(x[i]==1)45.{46.couti;47.}48.}49.coutendl;50.51.for(inti=0;i50;i++)52.{53.deletep[i];54.}55.56.delete[]p;57.58.return0;59.}60.61.templateclassType62.intKnapsack(intn,Typec,Typev[],Typew[],int**p,intx[])63.{64.int*head=newint[n+2];65.head[n+1]=0;66.67.p[0][0]=0;//p[][0]存储物品重量68.p[0][1]=0;//p[][1]存储物品价值，物品n的跳跃点（0，0）69.70.//left指向p[i+1]的第一个跳跃点，right指向最后一个71.//拿书上的例子来说，若计算p[3]=0;则left指向p[4]的第一跳跃点（00）right指向（9,10）72.intleft=0,right=0,next=1;//next即下一个跳跃点要存放的位置73.head[n]=1;//head[n]用来指向第n个物品第一个跳跃点的位置74.75.for(inti=n;i=1;i--)76.{77.intk=left;//k指向p[]中跳跃点,移动k来判断p[]与p[]+（wv）中的受控点78.for(intj=left;j=right;j++)79.{80.if(p[j][0]+w[i]c)break;//剩余的空间不能再装入i，退出for循环;81.Typey=p[j][0]+w[i],m=p[j]