背包问题详解

1,动态规划系列之二,背包问题,彭智朝2010.6.8,2,解空间,设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),root,0,1,0,1,0,1,0,1,0,4,0-1背包问题,问题陈述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。解题思路：此问题可转化为：给定c0，wi0，vi0，1in，要求找出一个n元0-1向量(x1，x2，xn)，xi0，1，1in，使得wixic，而且vixi达到最大。因此，0-1背包是一个特殊的整数规划问题：maxvixis.t.wixic，xi0，1，1in可用动态规划算法求解。,5,其他类型背包问题,完全背包问题(0/1)：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。多重背包问题有N种物品和一个容量为V的背包。第i种物品最多有ni件可用，每件费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。,6,0-1背包问题,设所给0-1背包问题的子问题,的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。,算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2n时，算法需要(n2n)计算时间。,7,0/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(1in)个物品中能够装入容量为j（1jC）的背包中的物品的最大值，则可以得到如下动态规划函数：,0-1背包问题,8,1、0-1背包问题动态规划算法,voidKnapsack(int*v,int*w,intc,intn,int*m)intj;intjMax;if(wn-1c)jMax=c;elsejMax=wn-1;for(j=0;j1;i-)intjMax;if(wn-1c)jMax=c;elsejMax=wn-1;for(j=0;jmi+1j-wi+vi)mij=mi+1j;elsemij=mi+1j-wi+vi;m1c=m2c;if(c=w1)m1c=(m1cm2c-w1+v1)?m1c:m2c-w1+v1);,9,根据动态规划函数，用一个(n+1)(C+1)的二维表V，Vij表示把前i个物品装入容量为j的背包中获得的最大价值。,例如，有5个物品，其重量分别是2,2,6,5,4，价值分别为6,3,5,4,6，背包的容量为10。,1、0-1背包问题动态规划算法举例,10,第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。,11,x5=1,x4=0,x3=0,x2=1,x1=1,12,voidTraceback(int*m,intw,intc,intn,intx)/计算xfor(inti=1;in;i+)if(mic=mi+1c)xi=0;elsexi=1;c-=wi;xn=(mnc)?1:0;,1、0-1背包问题动态规划算法,13,算法改进,由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1in)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全部跳跃点唯一确定。如图所示。,对每一个确定的i(1in)，用一个表pi存储函数m(i，j)的全部跳跃点。表pi可依计算m(i，j)的递归式递归地由表pi+1计算，初始时pn+1=(0，0)。,14,一个例子,n=3，c=6，w=4，3，2，v=5，2，1。,15,函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算得到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j)的跳跃点集pi+1与函数m(i+1，j-wi)+vi的跳跃点集qi+1的并集中。易知，(s,t)qi+1当且仅当wisc且(s-wi,t-vi)pi+1。因此，容易由pi+1确定跳跃点集qi+1如下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1另一方面，设(a，b)和(c，d)是pi+1qi+1中的2个跳跃点，则当ca且d,2、背包问题贪心算法,27,2、背包问题贪心算法,对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。,28,有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。,3、0-1背包问题回溯法,29,问题的解空间,问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。,注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。,n=3时的0-1背包问题用完全二叉树表示的解空间,30,3、0-1背包问题回溯法,n=3,C=30,w=16,15,15,v=45,25,25开始时，Cr=C=30，V=0，A为唯一活结点，也是当前扩展结点扩展A，先到达B结点Cr=Cr-w1=14，V=V+v1=45此时A、B为活结点，B成为当前扩展结点扩展B，先到达DCr45，皆得到一个可行解x=(0,1,1)，V=50L不可扩展，成为死结点，返回到F再扩展F到达MM是叶结点，且2550，不是最优解M不可扩展，成为死结点，返回到FF没有可扩展结点，成为死结点，返回到C再扩展C到达GCr=30，V=0，活结点为A、C、G，G为当前扩展结点扩展G，先到达N，N是叶结点，且2550，不是最优解，又N不可扩展，返回到G再扩展G到达O，O是叶结点，且050，不是最优解，又O不可扩展，返回到GG没有可扩展结点，成为死结点，返回到CC没有可扩展结点，成为死结点，返回到AA没有可扩展结点，成为死结点，算法结束，最优解X=(0,1,1)，最优值V=50,31,3、0-1背包问题回溯法,解空间：子集树可行性约束函数：上界函数：,01背包问题是一个子集选取问题，适合于用子集树表示01背包问题的解空间。在搜索解空间树是，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。,例如，对于0-1背包问题的一个实例，n=4,c=7,p=9,10,7,4，w=3,5,2,1。这4个物品的单位重量价值分别为3,2,3.5,4。以物品单位重量价值的递减序装入物品。首先装入物品4，然后装人物品3和10装人这3个物品后，剩余的背包容量为1，只能装人0.2的物品2。由此得到一个解为x=1,0.2,1,1，其相应的价值为22。尽管这个解不是一个可行解，但可以证明其价值是最优值的一个上界。因此，对于这个实例，最优值不超过22。,32,3、0-1背包问题回溯法,在实现时，由函数Bound来计算在当前结点处的上界。它是类Knap的私有成员。Knap的其他成员记录解空间树中的结点信息，以减少函数参数的传递以及递归调用时所需的栈空间。在解空问树的当前扩展结点处，仅当要进人右子树时才计算L界函数Bound,以判断是否可以将右子树剪去。进人左子树时不需计算上界，因为其上界与其父结点的上界相同。在调用函数Knapsack之前，需先将各物品依其单位重量价值从大到小排序。为此目的，我们定义了类Object。其中，n)if(bestpbestp)/搜索右子树xi=0;Backtrack(i+1);,35,3、0-1背包问题回溯法,templateTypepKnap:Bound(inti)/计算上界Typewcleft=c-cw;/剩余容量Typepb=cp;/以物品单位重量价值递减序装入物品while(i=n,36,3、0-1背包问题回溯法,templateclassObjectfriendintKnapsack(int*,int*,int,int);public:intoperator=a.d);private:intID;floatd;,37,templateintKnapsack(Typepp,Typeww,Typewc,intn)/为Knap:Backtrack初始化TypewW=0;TypepP=0;inti=1;Object*Q=newObjectn;for(i=1;i=n;i+)Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;if(W=c)returnP;/装入所有物品/依物品单位重量排序Sort(Q,n)floatf;for(i=0;in;i+)for(intj=i;jn;j+)if(Qi.dQj.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f;,KnapK;K.p=newintn+1;K.w=newintn+1;K.x=newintn+1;K.bestx=newintn+1;K.x0=0;K.bestx0=0;for(i=1;i=n;i+)K.pi=pQi-1.ID;K.wi=wQi-1.ID;K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;/回溯搜索K.Backtrack(1);K.print();deleteQ;deleteK.w;deleteK.p;returnK.bestp;,38,4、0-1背包问题分支限界法,分支限界法与回溯法,（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。,（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,39,分支限界法的基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。,40,4、0-1背包问题分支限界法,常见的两种分支限界法,（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。,（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,41,n=3时的0-1背包问题，用完全二叉树表示的解空间,实例如下：w=16,15,15,p=45,25,25,c=30。（1）队列式(FIFO)分支限界法（子集树）（2）优先队列式分支限界法（排列树）极大堆来表示活结点表的优先队列。,4、0-1背包问题分支限界法,42,4、0-1背包问题分支限界法,算法的思想,首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进