[理学]背包问题详解ppt课件

1、1 12解空间n设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）。23解空间图示n以3个物品为例,解(0,1,0)表示(不取物品0,取物品1,不取物品2)root01010101034n问题陈述：问题陈述：n给定给定n n种物品和一背包。物品种物品和一背包。物品i i的重量是的重量是wiwi，其价值为，其价值为vivi，背包的，背包的容量为容量为c c。问应如何选择装入背包中的物品，使得装入背包中物品。问应如何选择

2、装入背包中的物品，使得装入背包中物品的总价值最大？的总价值最大？n在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有两种选择，即装入背只有两种选择，即装入背包或不装入背包。不能将物品包或不装入背包。不能将物品i i装入背包多次，也不能只装入部分装入背包多次，也不能只装入部分的物品的物品i i。因此，该问题称为。因此，该问题称为0-10-1背包问题。背包问题。nn解题思路：解题思路：n此问题可转化为：给定此问题可转化为：给定c0c0，wi0wi0，vi0vi0，1in1in，要求找出一，要求找出一个个n n元元0-10-1向量向量(x1(x1，x2x2，xn)xn)，

3、xi0 xi0，11，1in1in，使得，使得wixicwixic，而且，而且vixivixi达到最大。因此，达到最大。因此，0-10-1背包是一个特殊的背包是一个特殊的整数规划问题：整数规划问题：n max vixi max vixin s.t. wixic s.t. wixic，n xi0 xi0，11，1in1inn可用动态规划算法求解。可用动态规划算法求解。45其他类型背包问题n完全背包问题完全背包问题(0/1)(0/1)：q有有N N种物品和一个容量为种物品和一个容量为V V的背包，每种物品都有的背包，每种物品都有无无限限件可用。第件可用。第i i种物品的费用是种物品的费用是cici

4、，价值是，价值是wiwi。求解将哪些物品装入背包可使这些物品的费用总和求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。不超过背包容量，且价值总和最大。n多重背包问题多重背包问题q有有N N种物品和一个容量为种物品和一个容量为V V的背包。第的背包。第i i种物品种物品最多最多有有nini件可用，每件费用是件可用，每件费用是cici，价值是，价值是wiwi。求。求解将哪些物品装入背包可使这些物品的费用总和不解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。超过背包容量，且价值总和最大。 56设所给设所给0-1背包问题的子问题背包问题的子问题ni

5、kkkxvmaxnkixjxwknikkk,1 , 0的最优值为的最优值为m(i，j)，即，即m(i，j)是背包容量为是背包容量为j，可选择物品为，可选择物品为i，i+1，n时时0-1背包问题的最优值。由背包问题的最优值。由0-1背包问题的最优子背包问题的最优子结构性质，可以建立计算结构性质，可以建立计算m(i，j)的递归式如下。的递归式如下。iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(nnnwjwjvjnm00),(算法复杂度分析：算法复杂度分析：从从m(i，j)的递归式容易看出，算法需要的递归式容易看出，算法需要O(nc)计算计算时间。当背包容量

6、时间。当背包容量c很大时，算法需要的计算时间较很大时，算法需要的计算时间较多。例如，当多。例如，当c2n时，算法需要时，算法需要(n2n)计算时间。计算时间。 67 0/1背包问题可以看作是决策一个序列背包问题可以看作是决策一个序列(x1, x2, , xn)，对任，对任一变量一变量xi的决策是决定的决策是决定xi=1还是还是xi=0。在对。在对xi-1决策后，已确定了决策后，已确定了(x1, , xi-1)，在决策，在决策xi时，问题处于下列两种状态之一：时，问题处于下列两种状态之一：（1）背包容量不足以装入物品）背包容量不足以装入物品i，则，则xi=0，背包不增加价值；，背包不增加价值；（

7、2）背包容量可以装入物品）背包容量可以装入物品i，则，则xi=1，背包的价值增加了，背包的价值增加了vi。 这两种情况下背包价值的最大者应该是这两种情况下背包价值的最大者应该是对对xi决策后决策后的背包的背包价值。令价值。令V(i, j)表示在表示在前前i(1in)个物品中能够装入容量为个物品中能够装入容量为j（1jC）的背包中的物品的最大值）的背包中的物品的最大值，则可以得到如下动态规，则可以得到如下动态规划函数：划函数： 78nvoid Knapsack(int *v, int *w, int c, int n, int * m)n int j; int jMax;n if(wn-1c)

8、jMax=c; else jMax=wn-1; n for (j = 0; j = jMax ;j+) mnj = 0; n for (j = wn; j 1; i-) n int jMax;n if(wn-1c) jMax=c; else jMax=wn-1;n for (j = 0; j = jMax; j+)n mij = mi+1j;n for (j = wi ; j mi+1j-wi + vi ) mij=mi+1j;n else mij=mi+1j-wi + vi ;n n m1c =m2c;n if (c = w1) m1c=(m1cm2c-w1+v1)?m1c:m2c-w1+v

9、1); n89 根据动态规划函数，用一个(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=65910 012345678910 00000000000w1=2 v1=6100666666666w2=2 v2=3200669999999w3=6 v3=5300669999111114w4=5 v4=4400669991

10、0111314w5=4 v5=6500669912121515150第一阶段，只装入前第一阶段，只装入前1个物品，确定在个物品，确定在各种情况下各种情况下的背包能够得到的最大价值；的背包能够得到的最大价值；第二阶段，只装入前第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第依此类推，直到第n个阶段。最后，个阶段。最后，V(n,C)便是在容量为便是在容量为C的背包中装入的背包中装入n个物品个物品时取得的最大价值。时取得的最大价值。1011x5=1x4=0 x3=0 x2=1x1=1 012345678910 0

11、0000000000w1=2 v1=6100666666666w2=2 v2=3200669999999w3=6 v3=5300669999111114w4=5 v4=44006699910111314w5=4 v5=65006699121215151501112nvoid Traceback(int *m, int w , int c, int n, int x )n/ 计算xnfor (int i=1; in; i+)nif (mic=mi+1c)n xi=0;nelse nnxi=1;n c-=wi;nnxn=(mnc)?1:0;n1213由由m(i,j)的递归式容易证明，在一般情况下，

12、对每一个确定的的递归式容易证明，在一般情况下，对每一个确定的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)。1314n=3，

13、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)1415函数函数m(i,j)是由函数是由函数m(i+1,j)与函数与函数m(i+1,j-wi)+vi作作max运运算得到的。因

14、此，函数算得到的。因此，函数m(i,j)的全部跳跃点包含于函数的全部跳跃点包含于函数m(i+1，j)的跳跃点集的跳跃点集pi+1与函数与函数m(i+1，j-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

15、且且db时，时，(c，d)受控于受控于(a，b)，从而，从而(c，d)不是不是pi中的跳跃点。除受控跳跃点外，中的跳跃点。除受控跳跃点外，pi+1 qi+1中的其它跳中的其它跳跃点均为跃点均为pi中的跳跃点。中的跳跃点。由此可见，在递归地由表由此可见，在递归地由表pi+1计算表计算表pi时，可先由时，可先由pi+1计算出计算出qi+1，然后合并表，然后合并表pi+1和表和表qi+1，并清除其中的受，并清除其中的受控跳跃点得到表控跳跃点得到表pi。1516n=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,

16、v5)=(4,6)。p5=(0,0),(4,6)。q5=p5(w4,v4)=(5,4),(9,10)。从跳跃点集p5与q5的并集p5q5=(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)，

17、(8，15)p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15)p1的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。1617上述算法的主要计算量在于计算跳跃点集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(

18、1in)是整数时，|pi|c+1，(1in)。在这种情况下，改进后算法的计算时间复杂性为O(minnc,2n)。 nniinniOOipO22| 1|221718 本节着重讨论可以用贪心算法求解的问题的一般特征。本节着重讨论可以用贪心算法求解的问题的一般特征。 对于一个具体的问题，怎么知道是否可用贪心算法解此问题，对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢以及能否得到问题的最优解呢? ?这个问题很难给予肯定的回答。这个问题很难给予肯定的回答。 但是，从许多可以用贪心算法求解的问题中看到这类问题一般但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有具

19、有2 2个重要的性质：贪心选择性质和最优子结构性质。个重要的性质：贪心选择性质和最优子结构性质。1819贪心算法的基本要素1 1、贪心选择性质、贪心选择性质 所谓所谓是指所求问题的是指所求问题的可以可以通过一系列通过一系列的选择，即贪心选择来达到。这是的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。规划算法的主要区别。 动态规划算法通常以动态规划算法通常以的方式解各子问题，的方式解各子问题，而贪心算法则通常以而贪心算法则通常以的方式进行，以迭代的方的方式进行，以迭代的方式作出相继的贪心选择，每作一

20、次贪心选择就将所求问式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。体最优解。1920贪心算法的基本要素 当一个问题的最优解包含其子问题的最优解时，称此问当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。动态

21、规划算法或贪心算法求解的关键特征。 2021 贪心算法和动态规划算法都要求问题具有最优子结构性贪心算法和动态规划算法都要求问题具有最优子结构性质，这是质，这是2 2类算法的一个共同点。但是，对于具有最优子结构类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解的问题应该选用贪心算法还是动态规划算法求解? ?是否能用动是否能用动态规划算法求解的问题也能用贪心算法求解态规划算法求解的问题也能用贪心算法求解? ?下面研究下面研究2 2个经典个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。差别。贪

22、心算法与动态规划算法的差异2122n0-10-1背包问题：背包问题： 给定给定n n种物品和一个背包。物品种物品和一个背包。物品i i的重量是的重量是WiWi，其价值为，其价值为ViVi，背包的容量为背包的容量为C C。应如何选择装入背包的物品，使得装入背包中物。应如何选择装入背包的物品，使得装入背包中物品的总价值最大品的总价值最大? ? 2223n背包问题：背包问题： 与与0-10-1背包问题类似，所不同的是在选择物品背包问题类似，所不同的是在选择物品i i装入背包时，装入背包时，可以选择物品可以选择物品i i的一部分，而不一定要全部装入背包，的一部分，而不一定要全部装入背包，1in1in。

23、 这这2 2类问题都具有类问题都具有性质，极为相似，但性质，极为相似，但背包问题可以用贪心算法求解，而背包问题可以用贪心算法求解，而0-10-1背包问题却不能背包问题却不能用贪心算法求解。用贪心算法求解。 2324 首先计算每种物品单位重量的价值首先计算每种物品单位重量的价值Vi/WiVi/Wi，然后，依贪心选择策，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过全部装入背包后，背包内的物品总重量未超过C C，则选择单位重量价，则选择单位重量价值次高的物品并尽可能多

24、地装入背包。依此策略一直地进行下去，直值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。到背包装满为止。 具体算法可描述如下页：具体算法可描述如下页： 用贪心算法解背包问题的基本步骤：2425nvoid Knapsack(int n,float M,float v,float w,float x)n Sort(n,v,w);n int i;n for (i=1;i=n;i+) xi=0;n float c=M;n for (i=1;ic) break;n xi=1;n c-=wi;n n if (i102030501.￥60 2.￥100 3.￥120 4.背包 =￥

25、220=￥160=￥180=￥2401002012030601010020601012030601010020802012020300-1背包问题的例子2627 对于对于0-10-1背包问题，贪心选择之所以不能得到最优解是因为在背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑间使每公斤背包空间的价值降低了。事实上，在考虑0-10-1背包问题背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后时，应比较选择该物品和不选择该物品所导

26、致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。问题可用动态规划算法求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解实际上也是如此，动态规划算法的确可以有效地解0-10-1背包问背包问题。题。 2728n有许多问题，当需要找出它的解集或者要求回答什么解是满足有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。某些约束条件的最佳解时，往往要使用回溯法。n回溯法的基本做法是搜索，或是一种组织得井井有条的，能避回溯法的基

27、本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。相当大的问题。n回溯法在问题的解空间树中，按深度优先策略，从根结点出发回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，根的子树的搜索，逐层向其祖先结点回溯；

28、否则，进入该子树，继续按深度优先策略搜索。继续按深度优先策略搜索。2829问题的解空间问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。所需表示的状态空间更小（存储量少，搜索方法简单）。n=3时的时的0-1背包问题用完全二叉树表示的解空间背包

29、问题用完全二叉树表示的解空间2930nn=3, C=30, w=16, 15, 15, v=45, 25, 25n开始时，Cr=C=30，V=0，A为唯一活结点，也是当前扩展结点n扩展A，先到达B结点qCr=Cr-w1=14，V=V+v1=45q此时A、B为活结点，B成为当前扩展结点q扩展B，先到达DnCrw2，D导致一个不可行解，回溯到Bq再扩展B到达EnE可行，此时A、B、E是活结点，E成为新的扩展结点n扩展E，先到达JqCr45，皆得到一个可行解x=(0,1,1)，V=50qL不可扩展，成为死结点，返回到Fn再扩展F到达MqM是叶结点，且2550，不是最优解qM不可扩展，成为死结点，返回

30、到FnF没有可扩展结点，成为死结点，返回到Cq再扩展C到达GnCr=30，V=0，活结点为A、C、G，G为当前扩展结点n扩展G，先到达N，N是叶结点，且2550，不是最优解，又N不可扩展，返回到Gn再扩展G到达O，O是叶结点，且050，不是最优解，又O不可扩展，返回到GnG没有可扩展结点，成为死结点，返回到CqC没有可扩展结点，成为死结点，返回到AnA没有可扩展结点，成为死结点，算法结束，最优解X=(0,1,1)，最优值V=50ACr=C=30，V=0Bw1=16，v1=45Cr=14，V=45C Cr=30，V=0DCrw2不可行解JCr45x=(0,1,1)Fw2=15，v2=25Cr=1

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

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

33、实例，最优值不超过证明其价值是最优值的一个上界。因此，对于这个实例，最优值不超过22。3132n在实现时，由函数在实现时，由函数BoundBound来计算在当前结点处的上界。来计算在当前结点处的上界。它是类它是类KnapKnap的私有成员。的私有成员。KnapKnap的其他成员记录解空间树的其他成员记录解空间树中的结点信息，以减少函数参数的传递以及递归调用时中的结点信息，以减少函数参数的传递以及递归调用时所需的栈空间。在解空问树的当前扩展结点处，仅当要所需的栈空间。在解空问树的当前扩展结点处，仅当要进人右子树时才计算进人右子树时才计算L L界函数界函数Bound,Bound,以判断是否可以将以

34、判断是否可以将右子树剪去。进人左子树时不需计算上界，因为其上界右子树剪去。进人左子树时不需计算上界，因为其上界与其父结点的上界相同。与其父结点的上界相同。n 在调用函数在调用函数KnapsackKnapsack之前，需先将各物品依其单位重之前，需先将各物品依其单位重量价值从大到小排序。为此目的，我们定义了类量价值从大到小排序。为此目的，我们定义了类ObjectObject。其中，其中，=运算符与通常的定义相反，其口的是为了方便运算符与通常的定义相反，其口的是为了方便调用已有的排序算法。在通常情况下，排序算法将待排调用已有的排序算法。在通常情况下，排序算法将待排序元素从小到大排列。序元素从小到大

35、排列。3233templateclass 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;/当前价值当前价值 Typep bestp;/当前最优值当前最优值 Typep *bestx;/当前最优解当前最优解 Typep *

36、x;/当前解当前解; 3334templatevoid 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); 3435templateTypep Knap:Bound(int i)/ 计算上界计算上界 Typew cleft = c - cw; / 剩余容量剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品以物品单位重量价值递减序装入物品 while

37、 (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包装满背包 if (i = n) b += pi/wi * cleft; return b;3536templateclass Object friend int Knapsack(int *,int *,int ,int );public:int operator=a.d);private:int ID;float d; 3637templateint Knapsack(Typep p, Typew w, Typew c,int n)/为为Knap:Backtrack初始化初始化

38、 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) 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

39、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; 3738分支限界法与回溯法（1 1）求解目标：回溯法的求解目标是找出解空间树中满足）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出

40、满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。意义下的最优解。 （2 2）搜索方式的不同：回溯法以深度优先的方式搜索）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树先的方式搜索解空间树。 3839分支限界法的基本思想分支限界法的基本思想 分支限界法常以广度优先或以最小耗费（最大效益）分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树

41、。优先的方式搜索问题的解空间树。 此后，从活结点表中取下一结点成为当前扩展结点，此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。需的解或活结点表为空时为止。 在分支限界法中，每一个活结点只有一次机会成为在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中