背包问题详解

1动态规划系列之二背包问题彭智朝2010.6.82解空间设Xi表示第i件物品的取舍，1代表取，0代表舍，搜索的空间为n元一维数组（X1,X2,X3,……，Xn）,取值范围为（0，0，0……，0，0），（0，0，0……，0，1），（0，0，0……，1，0），（0，0，0……，1，1），……，（1，1，1……，1，1）。3解空间图示以3个物品为例,解(0,1,0)表示(不取物品0,取物品1,不取物品2)root01010101040-1背包问题问题陈述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。解题思路：此问题可转化为：给定c0，wi0，vi0，1≤i≤n，要求找出一个n元0-1向量(x1，x2，…，xn)，xi∈{0，1}，1≤i≤n，使得∑wixi≤c，而且∑vixi达到最大。因此，0-1背包是一个特殊的整数规划问题：max∑vixis.t.∑wixi≤c，xi∈{0，1}，1≤i≤n可用动态规划算法求解。5其他类型背包问题完全背包问题(0/1)：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。多重背包问题有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。60-1背包问题设所给0-1背包问题的子问题nikkkxvmaxnkixjxwknikkk},1,0{的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。iiiiwjwjjimvwjimjimjim0),1(}),1(),,1(max{),(nnnwjwjvjnm00),(算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2n时，算法需要Ω(n2n)计算时间。70/1背包问题可以看作是决策一个序列(x1,x2,…,xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1,…,xi-1)，在决策xi时，问题处于下列两种状态之一：（1）背包容量不足以装入物品i，则xi=0，背包不增加价值；（2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i,j)表示在前i(1≤i≤n)个物品中能够装入容量为j（1≤j≤C）的背包中的物品的最大值，则可以得到如下动态规划函数：0-1背包问题81、0-1背包问题—动态规划算法voidKnapsack(int*v,int*w,intc,intn,int**m){intj;intjMax;if(w[n]-1c)jMax=c;elsejMax=w[n]-1;for(j=0;j=jMax;j++)m[n][j]=0;for(j=w[n];j=c;j++)m[n][j]=v[n];for(inti=n-1;i1;i--){intjMax;if(w[n]-1c)jMax=c;elsejMax=w[n]-1;for(j=0;j=jMax;j++)m[i][j]=m[i+1][j];for(j=w[i];j=c;j++)if(m[i+1][j]m[i+1][j-w[i]]+v[i])m[i][j]=m[i+1][j];elsem[i][j]=m[i+1][j-w[i]]+v[i];}m[1][c]=m[2][c];if(c=w[1])m[1][c]=((m[1][c]m[2][c-w[1]]+v[1])?m[1][c]:m[2][c-w[1]]+v[1]);}9根据动态规划函数，用一个(n+1)×(C+1)的二维表V，V[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。例如，有5个物品，其重量分别是{2,2,6,5,4}，价值分别为{6,3,5,4,6}，背包的容量为10。0123456789100w1=2v1=61w2=2v2=32w3=6v3=53w4=5v4=44w5=4v5=651、0-1背包问题—动态规划算法举例1001234567891000000000000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w4=5v4=44006699910111314w5=4v5=6500669912121515150第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。11x5=1x4=0x3=0x2=1x1=101234567891000000000000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w4=5v4=44006699910111314w5=4v5=650066991212151515012voidTraceback(int**m,intw[],intc,intn,intx[]){//计算xfor(inti=1;in;i++)if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}x[n]=(m[n][c])?1:0;}1、0-1背包问题—动态规划算法13算法改进由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)}。14一个例子n=3，c=6，w={4，3，2}，v={5，2，1}。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)15•函数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]。算法改进16一个例子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。17上述算法的主要计算量在于计算跳跃点集p[i](1≤i≤n)。由于q[i+1]=p[i+1](wi，vi)，故计算q[i+1]需要O(|p[i+1]|)计算时间。合并p[i+1]和q[i+1]并清除受控跳跃点也需要O(|p[i+1]|)计算时间。从跳跃点集p[i]的定义可以看出，p[i]中的跳跃点相应于xi,…,xn的0/1赋值。因此，p[i]中跳跃点个数不超过2n-i+1。由此可见，算法计算跳跃点集p[i]所花费的计算时间为从而，改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1≤i≤n)是整数时，|p[i]|≤c+1，(1≤i≤n)。在这种情况下，改进后算法的计算时间复杂性为O(min{nc,2n})。算法复杂度分析nniinniOOipO22|]1[|22182、背包问题—贪心算法本节着重讨论可以用贪心算法求解的问题的一般特征。对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。19贪心算法的基本要素1、贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。20贪心算法的基本要素当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。2、最优子结构性质212、背包问题—贪心算法贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下