背包問題詳解.ppt

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）。3解空間圖示n以3個物品為例,解(0,1,0)表示(不取物品0,取物品1,不取物品2)root0101010104n問題陳述：問題陳述：n給定給定n n種物品和一背包。物品種物品和一背包。物品i i的重量是的重量是wiwi，其價值為，其價值為vivi，背包的，背包的容量為容量為c c。問應如何選擇裝入背包中的物品，使得裝入背包中物品。問應如何選擇裝入背包

2、中的物品，使得裝入背包中物品的總價值最大？的總價值最大？n在選擇裝入背包的物品時，對每種物品在選擇裝入背包的物品時，對每種物品i i只有兩種選擇，即裝入背只有兩種選擇，即裝入背包或不裝入背包。不能將物品包或不裝入背包。不能將物品i i裝入背包多次，也不能只裝入部分裝入背包多次，也不能只裝入部分的物品的物品i i。因此，該問題稱為。因此，該問題稱為0-10-1背包問題。背包問題。nn解題思路：解題思路：n此問題可轉化為：給定此問題可轉化為：給定c0c0，wiwi00，vi0vi0，1in1in，要求找出一，要求找出一個個n n元元0-10-1向量向量(x1(x1，x2x2，xnxn) )，xi0

3、 xi0，11，1in1in，使得，使得wixicwixic，而且，而且vixivixi達到最大。因此，達到最大。因此，0-10-1背包是一個特殊的背包是一個特殊的整數規(guī)劃問題：整數規(guī)劃問題：n max max vixivixin s.ts.t. . wixicwixic，n xi0 xi0，11，1in1inn可用動態(tài)規(guī)劃算法求解?？捎脛討B(tài)規(guī)劃算法求解。5其他類型背包問題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 。求。求解將哪些物品裝入背包可使這些物品的費用總和不解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。超過背包容量，且價值總和最大。 6設所給設所給0-1背包問題的子問題背包問題的子問題nikk

5、kxvmaxnkixjxwknikkk,1 , 0的最優(yōu)值為的最優(yōu)值為m(i，j)，即，即m(i，j)是背包容量為是背包容量為j，可選擇物品為，可選擇物品為i，i+1，n時時0-1背包問題的最優(yōu)值。由背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子背包問題的最優(yōu)子結構性質，可以建立計算結構性質，可以建立計算m(i，j)的遞歸式如下。的遞歸式如下。iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(nnnwjwjvjnm00),(算法復雜度分析：算法復雜度分析：從從m(i，j)的遞歸式容易看出，算法需要的遞歸式容易看出，算法需要o(nc)計算計算時間。當背包容量時間

6、。當背包容量c很大時，算法需要的計算時間較很大時，算法需要的計算時間較多。例如，當多。例如，當c2n時，算法需要時，算法需要(n2n)計算時間。計算時間。 7 0/1背包問題可以看作是決策一個序列背包問題可以看作是決策一個序列(x1, x2, , xn)，對任對任一變量一變量xi的決策是決定的決策是決定xi=1還是還是xi=0。在對在對xi-1決策后，已確定了決策后，已確定了(x1, , xi-1)，在決策在決策xi時，問題處于下列兩種狀態(tài)之一：時，問題處于下列兩種狀態(tài)之一：（1）背包容量不足以裝入物品）背包容量不足以裝入物品i，則，則xi=0，背包不增加價值；背包不增加價值；（2）背包容量可

7、以裝入物品）背包容量可以裝入物品i，則，則xi=1，背包的價值增加了背包的價值增加了vi。 這兩種情況下背包價值的最大者應該是這兩種情況下背包價值的最大者應該是對對xi決策后決策后的背包的背包價值。令價值。令v(i, j)表示在表示在前前i(1in)個物品中能夠裝入容量為個物品中能夠裝入容量為j（1jc）的背包中的物品的最大值的背包中的物品的最大值，則可以得到如下動態(tài)規(guī)，則可以得到如下動態(tài)規(guī)劃函數：劃函數： 8nvoid knapsack(int *v, int *w, int c, int n, int * m)n int j; int jmax;n if(wn-1c) jmax=c; el

8、se 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+v1); n9 根據動

9、態(tài)規(guī)劃函數，用一個(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=6510 012345678910 00000000000w1=2 v1=6100666666666w2=2 v2=3200669999999w3=6 v3=5300669999111114w4=5 v4=44006699910111314w5=4

10、v5=6500669912121515150第一階段，只裝入前第一階段，只裝入前1個物品，確定在個物品，確定在各種情況下各種情況下的背包能夠得到的最大價值；的背包能夠得到的最大價值；第二階段，只裝入前第二階段，只裝入前2個物品，確定在各種情況下的背包能夠得到的最大價值；個物品，確定在各種情況下的背包能夠得到的最大價值；依此類推，直到第依此類推，直到第n個階段。最后，個階段。最后，v(n,c)便是在容量為便是在容量為c的背包中裝入的背包中裝入n個物品個物品時取得的最大價值。時取得的最大價值。11x5=1x4=0 x3=0 x2=1x1=1 012345678910 00000000000w1=2

11、 v1=6100666666666w2=2 v2=3200669999999w3=6 v3=5300669999111114w4=5 v4=44006699910111314w5=4 v5=650066991212151515012nvoid 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;n13由由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)。14n=3，c=6，w=4，3，2，v=5，2，1。

13、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)的全

14、部跳躍點包含于函數的全部跳躍點包含于函數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且且db時，時，(c，d)受控于受控于(a，

15、b)，從而，從而(c，d)不是不是pi中的跳躍點。除受控跳躍點外，中的跳躍點。除受控跳躍點外，pi+1 qi+1中的其它跳中的其它跳躍點均為躍點均為pi中的跳躍點。中的跳躍點。由此可見，在遞歸地由表由此可見，在遞歸地由表pi+1計算表計算表pi時，可先由時，可先由pi+1計算出計算出qi+1，然后合并表，然后合并表pi+1和表和表qi+1，并清除其中的受，并清除其中的受控跳躍點得到表控跳躍點得到表pi。16n=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)

16、。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)，(8，15)p1=(0，0)，(2，6)，(4，

17、9)，(6，12)，(8，15)p1的最后的那個跳躍點(8,15)給出所求的最優(yōu)值為m(1,c)=15。17上述算法的主要計算量在于計算跳躍點集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)。在這種

18、情況下，改進后算法的計算時間復雜性為o(minnc,2n)。 nniinniooipo22| 1|2218 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。本節(jié)著重討論可以用貪心算法求解的問題的一般特征。 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢以及能否得到問題的最優(yōu)解呢? ?這個問題很難給予肯定的回答。這個問題很難給予肯定的回答。 但是，從許多可以用貪心算法求解的問題中看到這類問題一般但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有具有2 2個重要的性質：貪心選擇性質和最優(yōu)子結構性質。個重

19、要的性質：貪心選擇性質和最優(yōu)子結構性質。19貪心算法的基本要素1 1、貪心選擇性質、貪心選擇性質 所謂所謂是指所求問題的是指所求問題的可以可以通過一系列通過一系列的選擇，即貪心選擇來達到。這是的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。規(guī)劃算法的主要區(qū)別。 動態(tài)規(guī)劃算法通常以動態(tài)規(guī)劃算法通常以的方式解各子問題，的方式解各子問題，而貪心算法則通常以而貪心算法則通常以的方式進行，以迭代的方的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問式作出相繼的貪心選擇，每作一次貪心選擇就

20、將所求問題簡化為規(guī)模更小的子問題。題簡化為規(guī)模更小的子問題。 對于一個具體問題，要確定它是否具有貪心選擇性對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整質，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。體最優(yōu)解。20貪心算法的基本要素 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用題具有最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。 21 貪心算法和動態(tài)規(guī)劃算法

21、都要求問題具有最優(yōu)子結構性貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結構性質，這是質，這是2 2類算法的一個共同點。但是，對于具有最優(yōu)子結構類算法的一個共同點。但是，對于具有最優(yōu)子結構的問題應該選用貪心算法還是動態(tài)規(guī)劃算法求解的問題應該選用貪心算法還是動態(tài)規(guī)劃算法求解? ?是否能用動是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解態(tài)規(guī)劃算法求解的問題也能用貪心算法求解? ?下面研究下面研究2 2個經典個經典的組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主要的組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主要差別。差別。貪心算法與動態(tài)規(guī)劃算法的差異22n0-10-1背包問題：背包問題： 給

22、定給定n n種物品和一個背包。物品種物品和一個背包。物品i i的重量是的重量是wiwi，其價值為，其價值為vivi，背包的容量為背包的容量為c c。應如何選擇裝入背包的物品，使得裝入背包中物。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大品的總價值最大? ? 23n背包問題：背包問題： 與與0-10-1背包問題類似，所不同的是在選擇物品背包問題類似，所不同的是在選擇物品i i裝入背包時，裝入背包時，可以選擇物品可以選擇物品i i的一部分，而不一定要全部裝入背包，的一部分，而不一定要全部裝入背包，1in1in。 這這2 2類問題都具有類問題都具有性質，極為相似，但性質，極為相似，但背包

23、問題可以用貪心算法求解，而背包問題可以用貪心算法求解，而0-10-1背包問題卻不能背包問題卻不能用貪心算法求解。用貪心算法求解。 24 首先計算每種物品單位重量的價值首先計算每種物品單位重量的價值vi/vi/wiwi，然后，依貪心選擇策，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品總重量未超過全部裝入背包后，背包內的物品總重量未超過c c，則選擇單位重量價，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直值次高的物品并盡可能多地裝入背包。依此策略

24、一直地進行下去，直到背包裝滿為止。到背包裝滿為止。 具體算法可描述如下頁：具體算法可描述如下頁： 用貪心算法解背包問題的基本步驟：25nvoid 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.背包 =￥220=￥160=￥180=￥240100201203060101002060101

25、2030601010020802012020300-1背包問題的例子27 對于對于0-10-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮間使每公斤背包空間的價值降低了。事實上，在考慮0-10-1背包問題背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。由此就導出許多互相重疊的子問題。這正是該再作出最好選擇

26、。由此就導出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。問題可用動態(tài)規(guī)劃算法求解的另一重要特征。實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-10-1背包問背包問題。題。 28n有許多問題，當需要找出它的解集或者要求回答什么解是滿足有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。某些約束條件的最佳解時，往往要使用回溯法。n回溯法的基本做法是搜索，或是一種組織得井井有條的，能避回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些

27、組合數免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數相當大的問題。相當大的問題。n回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對該結點為結點是否包含問題的解。如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。繼續(xù)按深度優(yōu)先策略搜索。29問題的解空間問題的解向

28、量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）。所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）。n=3時的時的0-1背包問題用完全二叉樹表示的解空間背包問題用完全二叉樹表示的解空間30nn=3, c=30, w=16, 15, 15, v=45,

29、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，不是最優(yōu)解qm不可擴展，成為死結點，返回到fnf沒有可擴展結點，成為死結點，返回到cq再擴展c到達gncr=30，v=0，活結點為a、c、g

30、，g為當前擴展結點n擴展g，先到達n，n是葉結點，且2550，不是最優(yōu)解，又n不可擴展，返回到gn再擴展g到達o，o是葉結點，且050，不是最優(yōu)解，又o不可擴展，返回到gng沒有可擴展結點，成為死結點，返回到cqc沒有可擴展結點，成為死結點，返回到ana沒有可擴展結點，成為死結點，算法結束，最優(yōu)解x=(0,1,1)，最優(yōu)值v=50acr=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不是最優(yōu)解31解空間：子集樹解空間：子集樹可行性約束函數：可行性約束函數：上界

31、函數：上界函數：11cxwniii 01背包問題是一個子集選取問題，背包問題是一個子集選取問題，適合于用子集樹表示適合于用子集樹表示01背包問題的解空間。背包問題的解空間。在搜索解空間樹是，只要其左兒子節(jié)點是一在搜索解空間樹是，只要其左兒子節(jié)點是一個可行結點，搜索就進入左子樹，在右子樹個可行結點，搜索就進入左子樹，在右子樹中有可能包含最優(yōu)解是才進入右子樹搜索。中有可能包含最優(yōu)解是才進入右子樹搜索。否則將右子樹剪去。否則將右子樹剪去。 例如，對于例如，對于0-1背包問題的一個實例，背包問題的一個實例，n=4,c=7, p=9,10,7,4，w=3,5,2,1。這。這4個物品的單位重量價值分別為個

32、物品的單位重量價值分別為3,2,3.5,4。以物品單位。以物品單位重量價值的遞減序裝入物品。首先裝入物品重量價值的遞減序裝入物品。首先裝入物品4，然后裝人物品，然后裝人物品3和和10裝人這裝人這3個物品后，剩余的背包容量為個物品后，剩余的背包容量為1，只能裝人，只能裝人0.2的物品的物品2。由此得到一個解為。由此得到一個解為x=1,0.2,1,1，其相應的價值為，其相應的價值為22。盡管這個解不是一個可行解，但可以。盡管這個解不是一個可行解，但可以證明其價值是最優(yōu)值的一個上界。因此，對于這個實例，最優(yōu)值不超過證明其價值是最優(yōu)值的一個上界。因此，對于這個實例，最優(yōu)值不超過22。32n在實現時，由

33、函數在實現時，由函數boundbound來計算在當前結點處的上界。來計算在當前結點處的上界。它是類它是類knapknap的私有成員。的私有成員。knapknap的其他成員記錄解空間樹的其他成員記錄解空間樹中的結點信息，以減少函數參數的傳遞以及遞歸調用時中的結點信息，以減少函數參數的傳遞以及遞歸調用時所需的?？臻g。在解空問樹的當前擴展結點處，僅當要所需的?？臻g。在解空問樹的當前擴展結點處，僅當要進人右子樹時才計算進人右子樹時才計算l l界函數界函數bound,bound,以判斷是否可以將以判斷是否可以將右子樹剪去。進人左子樹時不需計算上界，因為其上界右子樹剪去。進人左子樹時不需計算上界，因為其上

34、界與其父結點的上界相同。與其父結點的上界相同。n 在調用函數在調用函數knapsackknapsack之前，需先將各物品依其單位重之前，需先將各物品依其單位重量價值從大到小排序。為此目的，我們定義了類量價值從大到小排序。為此目的，我們定義了類objectobject。其中，其中，=運算符與通常的定義相反，其口的是為了方便運算符與通常的定義相反，其口的是為了方便調用已有的排序算法。在通常情況下，排序算法將待排調用已有的排序算法。在通常情況下，排序算法將待排序元素從小到大排列。序元素從小到大排列。33templateclass knapfriend typep knapsack(typep *,t

35、ypew*, 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;/當前最優(yōu)值當前最優(yōu)值 typep *bestx;/當前最優(yōu)解當前最優(yōu)解 typep *x;/當前解當前解; 34templatevoid knap :backtrack(int i) if(in)

36、if(bestpcp) for(int j=1;j=n;j+) bestxj=xj; bestp=cp; return; if(cw+wibestp)/搜索右子樹搜索右子樹 xi=0; backtrack(i+1); 35templatetypep knap:bound(int i)/ 計算上界計算上界 typew cleft = c - cw; / 剩余容量剩余容量 typep b = cp; / 以物品單位重量價值遞減序裝入物品以物品單位重量價值遞減序裝入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 裝滿背包裝滿背包 i

37、f (i = n) b += pi/wi * cleft; return b;36templateclass object friend int knapsack(int *,int *,int ,int );public:int operator=a.d);private:int id;float d; 37templateint 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+)

38、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 intn+1;k.bestx = new intn+1;k.x0=0;k.bestx0=0;for( i=1;i=n;i+) k.pi=

39、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; 38分支限界法與回溯法（1 1）求解目標：）求解目標：回溯法的求解目標是找出解空間樹中滿足回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種約束條件的一個解，或是在滿足約束

40、條件的解中找出在某種意義下的最優(yōu)解。意義下的最優(yōu)解。 （2 2）搜索方式的不同：）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹先的方式搜索解空間樹。 39分支限界法的基本思想分支限界法的基本思想 分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。優(yōu)先的方式搜索問題的解空間樹。 此后，從活結點表中取下一結點成為當前擴展結點，此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續(xù)到找到所并重復上述結點擴展過程。這個過程一直持續(xù)到找到所需的解或活結點表為空時為止。需的解或活結點表為空時為止。 在分支限界法中，每一個活結點只有一次機會成為在分支限界法中，每一個活結點只有一次機會成為擴展結點?；罱Y點一旦成為擴展結點，就一次性產生其擴展結點?；罱Y點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優(yōu)解的兒子結點被舍棄，其余兒子結點被加入活致非最優(yōu)解的兒子結點被舍棄，其余兒子結點