理学背包问题详解PPT学习教案

1、会计学1理学背包问题详解理学背包问题详解2root010101010第1页/共43页3第2页/共43页4第3页/共43页5设所给设所给0-1背包问题的子问题背包问题的子问题nikkkxvmaxnkixjxwknikkk,1 , 0的最优值为的最优值为m(i，j)，即，即m(i，j)是背包容量为是背包容量为j，可选择物品为，可选择物品为i，i+1，n时时0-1背包问题的最优值。由背包问题的最优值。由0-1背包问题的最优背包问题的最优子结构性质，可以建立计算子结构性质，可以建立计算m(i，j)的递归式如下。的递归式如下。iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(m

2、ax),(nnnwjwjvjnm00),(算法复杂度分析：算法复杂度分析：从从m(i，j)的递归式容易看出，算法需要的递归式容易看出，算法需要O(nc)计算计算时间。当背包容量时间。当背包容量c很大时，算法需要的计算时间较很大时，算法需要的计算时间较多。例如，当多。例如，当c2n时，算法需要时，算法需要(n2n)计算时间。计算时间。 第4页/共43页6 0/1背包问题可以看作是决策一个序列背包问题可以看作是决策一个序列(x1, x2, , xn)，对任，对任一变量一变量xi的决策是决定的决策是决定xi=1还是还是xi=0。在对。在对xi-1决策后，已确定了决策后，已确定了(x1, , xi-1

3、)，在决策，在决策xi时，问题处于下列两种状态之一：时，问题处于下列两种状态之一：（1）背包容量不足以装入物品）背包容量不足以装入物品i，则，则xi=0，背包不增加价值；，背包不增加价值；（2）背包容量可以装入物品）背包容量可以装入物品i，则，则xi=1，背包的价值增加了，背包的价值增加了vi。 这两种情况下背包价值的最大者应该是这两种情况下背包价值的最大者应该是对对xi决策后决策后的背包的背包价值。令价值。令V(i, j)表示在表示在前前i(1in)个物品中能够装入容量为个物品中能够装入容量为j（1jC）的背包中的物品的最大值）的背包中的物品的最大值，则可以得到如下动态规划，则可以得到如下动

4、态规划函数：函数： 第5页/共43页7第6页/共43页8 根据动态规划函数，用一个(n+1)(C+1)的二维表V，Vij表示把前i个物品装入容量为j的背包中获得的最大价值。 例如，有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。 012345678910 0w1=2 v1=61w2=2 v2=32w3=6 v3=53w4=5 v4=44w5=4 v5=65第7页/共43页9 012345678910 00000000000w1=2 v1=6100666666666w2=2 v2=3200669999999w3=6 v3=5300669

5、999111114w4=5 v4=44006699910111314w5=4 v5=6500669912121515150第一阶段，只装入前第一阶段，只装入前1个物品，确定在个物品，确定在各种情况下各种情况下的背包能够得到的最大价值；的背包能够得到的最大价值；第二阶段，只装入前第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第依此类推，直到第n个阶段。最后，个阶段。最后，V(n,C)便是在容量为便是在容量为C的背包中装入的背包中装入n个物品个物品时取得的最大价值。时取得的最大价值。第8页/共43页10 x5=

6、1x4=0 x3=0 x2=1x1=1 012345678910 00000000000w1=2 v1=6100666666666w2=2 v2=3200669999999w3=6 v3=5300669999111114w4=5 v4=44006699910111314w5=4 v5=6500669912121515150第9页/共43页11第10页/共43页12由由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的的递归式容易证明，在一般情况下，对每一个确定的i(1in)，函数，函数m(i,j)是关于变量是关于变量j的阶梯状单调不减函数。跳跃的阶梯状单调不减函数。跳跃点是这一类函数的

7、描述特征。在一般情况下，函数点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其由其全部跳跃点唯一确定。如图所示。全部跳跃点唯一确定。如图所示。对每一个确定的对每一个确定的i(1in)，用一个表，用一个表pi存储函数存储函数m(i，j)的全部的全部跳跃点。表跳跃点。表pi可依计算可依计算m(i，j)的递归式递归地由表的递归式递归地由表pi+1计算计算，初始时，初始时pn+1=(0，0)。 第11页/共43页13n=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

8、)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)第12页/共43页14 函数函数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

9、-wi)+vi的跳跃点集的跳跃点集qi+1的的并集中。易知，并集中。易知，(s,t) qi+1当且仅当当且仅当wi s c且且(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+1 qi+1中的中的2个跳跃个跳跃点，则当点，则当c a且且db时，时，(c，d)受控于受控于(a，b)，从而，从而(c，d)不是不是pi中的跳跃点。除受控跳跃点外，中的跳跃点。除受控跳跃点外，pi+1 qi

10、+1中的其它跳中的其它跳跃点均为跃点均为pi中的跳跃点。中的跳跃点。 由此可见，在递归地由表由此可见，在递归地由表pi+1计算表计算表pi时，可先由时，可先由pi+1计算出计算出qi+1，然后合并表，然后合并表pi+1和表和表qi+1，并清除其，并清除其中的受控跳跃点得到表中的受控跳跃点得到表pi。第13页/共43页15n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。初始时p6=(0,0)，(w5,v5)=(4,6)。因此，q6=p6(w5,v5)=(4,6)。p5=(0,0),(4,6)。q5=p5(w4,v4)=(5,4),(9,10)。从跳跃点集p5与q5的并集p5q5

11、=(0,0),(4,6),(5,4),(9,10)中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p4=(0,0),(4,6),(9,10)q4=p4(6，5)=(6，5)，(10，11)p3=(0，0)，(4，6)，(9，10)，(10，11)q3=p3(2，3)=(2，3)，(6，9)p2=(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)q2=p2(2，6)=(2，6)，(4，9)，(6，12)，(8，15)p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15)p1的最后的那个跳跃点(8,15)给出所求的最优值为m(

12、1,c)=15。第14页/共43页16上述算法的主要计算量在于计算跳跃点集pi(1in)。由于qi+1=pi+1(wi，vi)，故计算qi+1需要O(|pi+1|)计算时间。合并pi+1和qi+1并清除受控跳跃点也需要O(|pi+1|)计算时间。从跳跃点集pi的定义可以看出，pi中的跳跃点相应于xi,xn的0/1赋值。因此，pi中跳跃点个数不超过2n-i+1。由此可见，算法计算跳跃点集pi所花费的计算时间为从而，改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1in)是整数时，|pi|c+1，(1in)。在这种情况下，改进后算法的计算时间复杂性为O(minnc,2n)。 nnii

13、nniOOipO22| 1|22第15页/共43页17第16页/共43页18 所谓所谓是指所求问题的是指所求问题的可以可以通过一系列通过一系列的选择，即贪心选择来达到。这是的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。规划算法的主要区别。 动态规划算法通常以动态规划算法通常以的方式解各子问题，的方式解各子问题，而贪心算法则通常以而贪心算法则通常以的方式进行，以迭代的方的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模

14、更小的子问题。题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。体最优解。第17页/共43页19第18页/共43页20贪心算法与动态规划算法的差异第19页/共43页21 第20页/共43页22 这这2 2类问题都具有类问题都具有性质，极为相似，但性质，极为相似，但背包问题可以用贪心算法求解，而背包问题可以用贪心算法求解，而0-10-1背包问题却不能背包问题却不能用贪心算法求解。用贪心算法求解。 第21页/共43页23用贪心算

15、法解背包问题的基本步骤：第22页/共43页24 算法算法knapsackknapsack的的主要计算时间在于将主要计算时间在于将各种物品依其单位重各种物品依其单位重量的价值从大到小排量的价值从大到小排序。因此，算法的计序。因此，算法的计算时间上界为算时间上界为O O（nlognnlogn）。）。为了证明算法的正确为了证明算法的正确性，还必须证明背包性，还必须证明背包问题具有贪心选择性问题具有贪心选择性质质。第23页/共43页25102030501.￥60 2.￥100 3.￥120 4.背包 =￥220=￥160=￥180=￥2401002012030601010020601012030601

16、010020802012020300-1背包问题的例子第24页/共43页26第25页/共43页27n有许多问题，当需要找出它的解集或者要求回答什么解是满足有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。某些约束条件的最佳解时，往往要使用回溯法。n回溯法的基本做法是搜索，或是一种组织得井井有条的，能避回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。相当大的问题。n回溯法在问题的解空间树中，按深度优先策略，从根结点出发回溯法

17、在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。，继续按深度优先策略搜索。第26页/共43页28问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施

18、加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。所需表示的状态空间更小（存储量少，搜索方法简单）。n=3时的时的0-1背包问题用完全二叉树表示的解空间背包问题用完全二叉树表示的解空间第27页/共43页29ACr=C=30，V=0Bw1=16，v1=45Cr=14，V=45C Cr=30，V=0DCrw2不可行解JCr45x=(0,1,1)Fw2=15，v2=25Cr=15，V=25M2550

19、不是最优解第28页/共43页30解空间：子集树解空间：子集树可行性约束函数：可行性约束函数：上界函数：上界函数：11cxwniii 01背包问题是一个子集选取问题，背包问题是一个子集选取问题，适合于用子集树表示适合于用子集树表示01背包问题的解空间背包问题的解空间。在搜索解空间树是，只要其左儿子节点是。在搜索解空间树是，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。否则将右子树剪去。 例如，对于例如，对于0-1背包问题的一个实例，背包问题的一个实例，n

20、=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。尽管这个解不是一个可行解，但可以。尽管这个解不是一个可行解，但可以证明其价值是最优值的一个上界。因此，对于这个实例，最优

21、值不超过证明其价值是最优值的一个上界。因此，对于这个实例，最优值不超过22。第29页/共43页31第30页/共43页32templateclass Knapfriend Typep Knapsack(Typep *,Typew*, Typew ,int );private: Typep Bound(int i); void Backtrack(int i); Typew c;/背包容量背包容量 int n; /物品数物品数Typew *w;/物品重量数组物品重量数组 Typep *p;/物品价值数组物品价值数组 Typew cw;/当前重量当前重量 Typep cp;/当前价值当前价值 Typ

22、ep bestp;/当前最优值当前最优值 Typep *bestx;/当前最优解当前最优解 Typep *x;/当前解当前解; 第31页/共43页33templatevoid Knap :Backtrack(int i) if(in) if(bestpcp) for(int j=1;j=n;j+) bestxj=xj; bestp=cp; return; if(cw+wibestp)/搜索右子树搜索右子树 xi=0; Backtrack(i+1); 第32页/共43页34templateTypep Knap:Bound(int i)/ 计算上界计算上界 Typew cleft = c - cw

23、; / 剩余容量剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包装满背包 if (i = n) b += pi/wi * cleft; return b;第33页/共43页35templateclass Object friend int Knapsack(int *,int *,int ,int );public:int operator=a.d);private:int ID;float d; 第34页/共43页3

24、6templateint Knapsack(Typep p, Typew w, Typew c,int n)/为为Knap:Backtrack初始化初始化 Typew W=0; Typep P=0;int i=1;Object *Q=new Objectn;for(i=1;i=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi;if(W=c)return P;/装入所有物品装入所有物品/依物品单位重量排序依物品单位重量排序Sort(Q,n)float f;for( i=0;in;i+) for(int j=i;jn;j+) if(Qi.dQj.d)

25、f=Qi.d;Qi.d=Qj.d;Qj.d=f; Knap K;K.p = new intn+1; K.w = new intn+1;K.x = new intn+1;K.bestx = new intn+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(); delete Q;delete K.w;delete K.p;return K.bestp; 第35页/共43页37分

26、支限界法与回溯法（1 1）求解目标：回溯法的求解目标是找出解空间树中满足）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。意义下的最优解。 （2 2）搜索方式的不同：回溯法以深度优先的方式搜索）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树先的方式搜索解空间树。 第

27、36页/共43页38 分支限界法常以广度优先或以最小耗费（最大效益分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。）优先的方式搜索问题的解空间树。 此后，从活结点表中取下一结点成为当前扩展结点此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。所需的解或活结点表为空时为止。 在分支限界法中，每一个活结点只有一次机会成为在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其扩展结点。活结点一旦成为扩展结点，就一次性

28、产生其所有儿子结点。在这些儿子结点中，导致不可行解或导所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。结点表中。第37页/共43页39常见的两种分支限界法（1 1）队列式）队列式( (FIFO)FIFO)分支限界法分支限界法 按照队列先进先出（按照队列先进先出（FIFOFIFO）原则选取下一个节点原则选取下一个节点为扩展节点。为扩展节点。 （2 2）优先队列式分支限界法）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。点成为当前扩展节点。第38页/共43页40n=3n=3时的时的0-10-1背包问题，用完全二叉树表示的解空间背包问题，用完全二叉树表示的解空间, ,实例实例如下：如下：w=16,15,15,p=45,25,25,c=30w=16,15,15,p=45,25,25,c=30。（1 1）队列式队列式( (FIFO)FIFO)分支限界法（子集树）分支限界法（子集树）（2 2）优先队列式分支限界法（排列树）优先队列式分支限界法（排列树） 极大堆来表示活结点表的优先队列。极大堆来表示活结点表的优先队列。第39页/共43页41算法的思想 首先，要对输入数据进行预处理，将