第3章动态规划-背包问题

给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包的容量为C。背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?如果在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或不装入背包，即不能将物品i装入背包多次，也不能只装入物品i的一部分，则称为0-1背包问题。3.100-1背包问题3.100-1背包问题考虑有三种物品,它们的重量为(w1,w2,w3)=(2,3,4),

价值为(v1,v2,v3)=(1,2,5),当背包容量为c=6时，如何装背包总价值最大？？{x1,x2,x3}={1,0,1}v1*x1+v2*x2+v3*x3=6{x1,x2,x3}={0,0,0}{0,0,1}{0,1,0}{1,0,0}{1,0,1}{1,1,0}常规方法：枚举

在0-1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：（式1）（式2）问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X=(x1,x2,…,xn)。3.100-1背包问题设(x1,x2,…,xn)是所给0-1背包问题的一个最优解，则(x2,…,xn)是下面一个子问题的最优解：如若不然，设(y2,…,yn)是上述子问题的一个最优解，则，且。因此，，这说明(x1,y2,…,yn)是所给0-1背包问题比(x1,x2,…,xn)更优的解，从而导致矛盾。背包问题的最优子结构性质设背包问题子问题的最优值为m(i,j),即m(i,j)是背包容量为j，可选择物品为i,i＋1,…,n时的最优值。当选择第i个物品时，。

如果不选择第i个物品，则。由背包问题的最优子结构性质，我们可以建立计算m(i,j)的递归式如下：m(i,j)=m(i+1,j-wi)+vim(i,j)=m(i+1,j)背包问题的递归关系背包问题算法描述voidKnapsack(Typev,intw,intc,intn,Type**m){intjMax=min(w[n]－1,c)//背包剩余容量//for(intj=0;j<=jMax;j++)//背包不同剩余容量jjMax<c//m[n][j]=0;for(intj=w[n];j<=c;j++)//背包不同剩余容量j>c//m[n][j]=v[n];for(inti=n-1;i>1;i--){jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)//背包不同剩余容量j

jMax<c//m[i][j]=m[i+1][j];//没产生任何效益//for(intj=w[i];j<=c;j++)//背包不同剩余容量j-wi

>c//m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}voidTraceback(Type**m,intw,intc,intn,intx){for(inti=1;i<n;i++)if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c=c-w[i];}x[n]=(m[n][c])?1:0;}背包问题算法描述算法复杂度分析：从m(i，j)的递归式容易看出，算法Knapsack需要O(nc)计算时间;Traceback需O(n)计算时间；算法总体需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2n时，算法需要Ω(n2n)计算时间。例:四个物品，背包容积为5，w[4]={2,1,3,2}，v[4]={12,10,20,15}，求最大价值m[1][c]及选取的物品编号4321432105000001015151515151520203535302537ijx4X3X2X11m[1][5]>m[2][5]所以物品1被选c–w[1]=3,查看m[2][3]>m[3][3]1j–w[2]=2,查看m[3][2]=m[4][2]0查看m[4][2]>01一个简单的例子m[1][5]<>m[2][5]4321432105000001010151515151520203535302537ij构造最优解x[1]=1c=5-w[1]=3m[2][3]<>m[3][3]x[2]=1c=3-w[2]=2m[3][2]=m[4][2]x[3]=0c=2m[4][2]<>0x[4]=10-1背包问题可以看作是决策一个序列(x1,x2,…,xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1,…,xi-1)，在决策xi时，问题处于下列两种状态之一：a.背包容量不足以装入物品i，则xi=0背包不增加价值；b.背包容量可以装入物品i，则xi=1背包的价值增加了vi。这两种情况下背包价值的最大者应该是对xi决策后的背包价值。背包问题解法二令m(i,j)表示在前i(1≤i≤n)个物品中能够装入容量为j（1≤j≤C）的背包中的物品的最大值，则可以得到如下动态规划函数：

m(i,0)=

m(0,j)=0（式3）式3表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。背包问题解法二式4的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包。（式4）背包问题解法二第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。（式4）背包问题解法二第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，m(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。为了确定装入背包的具体物品，从m(n,C)的值向前推，如果m(n,C)>m(n-1,C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量