背包問題詳解

1、12解空間n設(shè)Xi表示第i件物品的取舍，1代表取，0代表舍，搜索的空間為n元一維數(shù)組（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個(gè)物品為例,解(0,1,0)表示(不取物品0,取物品1,不取物品2)root0101010104n問題陳述：問題陳述：n給定給定n n種物品和一背包。物品種物品和一背包。物品i i的重量是的重量是wiwi，其價(jià)值為，其價(jià)值為vivi，背包的，背包的容量為容量為c c。問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品。問應(yīng)如何選擇裝入背包

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

3、 xi0，11，1in1in，使得，使得wixicwixic，而且，而且vixivixi達(dá)到最大。因此，達(dá)到最大。因此，0-10-1背包是一個(gè)特殊的背包是一個(gè)特殊的整數(shù)規(guī)劃問題：整數(shù)規(guī)劃問題：n max max vixivixin s.ts.t. . wixicwixic，n xi0 xi0，11，1in1inn可用動(dòng)態(tài)規(guī)劃算法求解。可用動(dòng)態(tài)規(guī)劃算法求解。5其他類型背包問題n完全背包問題完全背包問題(0/1)(0/1)：q有有N N種物品和一個(gè)容量為種物品和一個(gè)容量為V V的背包，每種物品都有的背包，每種物品都有無無限限件可用。第件可用。第i i種物品的費(fèi)用是種物品的費(fèi)用是cici ，價(jià)值是，

4、價(jià)值是wiwi 。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。不超過背包容量，且價(jià)值總和最大。n多重背包問題多重背包問題q有有N N種物品和一個(gè)容量為種物品和一個(gè)容量為V V的背包。第的背包。第i i種物品種物品最多最多有有nini 件可用，每件費(fèi)用是件可用，每件費(fèi)用是cici ，價(jià)值是，價(jià)值是wiwi 。求。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。超過背包容量，且價(jià)值總和最大。 6設(shè)所給設(shè)所給0-1背包問題的子問題背包問題的子問題nikk

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

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

7、以裝入物品）背包容量可以裝入物品i，則，則xi=1，背包的價(jià)值增加了背包的價(jià)值增加了vi。 這兩種情況下背包價(jià)值的最大者應(yīng)該是這兩種情況下背包價(jià)值的最大者應(yīng)該是對對xi決策后決策后的背包的背包價(jià)值。令價(jià)值。令V(i, j)表示在表示在前前i(1in)個(gè)物品中能夠裝入容量為個(gè)物品中能夠裝入容量為j（1jC）的背包中的物品的最大值的背包中的物品的最大值，則可以得到如下動(dòng)態(tài)規(guī)，則可以得到如下動(dòng)態(tài)規(guī)劃函數(shù)：劃函數(shù)： 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 根據(jù)動(dòng)

9、態(tài)規(guī)劃函數(shù)，用一個(gè)(n+1)(C+1)的二維表V，Vij表示把前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值。 例如，有5個(gè)物品，其重量分別是2, 2, 6, 5, 4，價(jià)值分別為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個(gè)物品，確定在個(gè)物品，確定在各種情況下各種情況下的背包能夠得到的最大價(jià)值；的背包能夠得到的最大價(jià)值；第二階段，只裝入前第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；依此類推，直到第依此類推，直到第n個(gè)階段。最后，個(gè)階段。最后，V(n,C)便是在容量為便是在容量為C的背包中裝入的背包中裝入n個(gè)物品個(gè)物品時(shí)取得的最大價(jià)值。時(shí)取得的最大價(jià)值。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/ 計(jì)算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)的遞歸式容易證明，在一般情況下，對每一個(gè)確定的的遞歸式容易證明，在一

12、般情況下，對每一個(gè)確定的i(1in)，函數(shù)，函數(shù)m(i,j)是關(guān)于變量是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類函數(shù)的描述特征。在一般情況下，函數(shù)點(diǎn)是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由其由其全部跳躍點(diǎn)唯一確定。如圖所示。全部跳躍點(diǎn)唯一確定。如圖所示。對每一個(gè)確定的對每一個(gè)確定的i(1in)，用一個(gè)表，用一個(gè)表pi存儲(chǔ)函數(shù)存儲(chǔ)函數(shù)m(i，j)的全部的全部跳躍點(diǎn)。表跳躍點(diǎn)。表pi可依計(jì)算可依計(jì)算m(i，j)的遞歸式遞歸地由表的遞歸式遞歸地由表pi+1計(jì)算，計(jì)算，初始時(shí)初始時(shí)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函數(shù)函數(shù)m(i,j)是由函數(shù)是由函數(shù)m(i+1,j)與函數(shù)與函數(shù)m(i+1,j-wi)+vi作作max運(yùn)運(yùn)算得到的。因此，函數(shù)算得到的。因此，函數(shù)m(i,j)的全

14、部跳躍點(diǎn)包含于函數(shù)的全部跳躍點(diǎn)包含于函數(shù)m(i+1，j)的跳躍點(diǎn)集的跳躍點(diǎn)集pi+1與函數(shù)與函數(shù)m(i+1，j-wi)+vi的跳躍點(diǎn)集的跳躍點(diǎn)集qi+1的的并集中。易知，并集中。易知，(s,t) qi+1當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)wi s c且且(s-wi,t-vi) pi+1。因此，容易由。因此，容易由pi+1確定跳躍點(diǎn)集確定跳躍點(diǎn)集qi+1如下如下qi+1=pi+1 (wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j) pi+1另一方面，設(shè)另一方面，設(shè)(a，b)和和(c，d)是是pi+1 qi+1中的中的2個(gè)跳躍個(gè)跳躍點(diǎn)，則當(dāng)點(diǎn)，則當(dāng)c a且且db時(shí)，時(shí)，(c，d)受控于受控于(a，

15、b)，從而，從而(c，d)不是不是pi中的跳躍點(diǎn)。除受控跳躍點(diǎn)外，中的跳躍點(diǎn)。除受控跳躍點(diǎn)外，pi+1 qi+1中的其它跳中的其它跳躍點(diǎn)均為躍點(diǎn)均為pi中的跳躍點(diǎn)。中的跳躍點(diǎn)。由此可見，在遞歸地由表由此可見，在遞歸地由表pi+1計(jì)算表計(jì)算表pi時(shí)，可先由時(shí)，可先由pi+1計(jì)算出計(jì)算出qi+1，然后合并表，然后合并表pi+1和表和表qi+1，并清除其中的受，并清除其中的受控跳躍點(diǎn)得到表控跳躍點(diǎn)得到表pi。16n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。初始時(shí)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)。從跳躍點(diǎn)集p5與q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中看到跳躍點(diǎn)(5,4)受控于跳躍點(diǎn)(4,6)。將受控跳躍點(diǎn)(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的最后的那個(gè)跳躍點(diǎn)(8,15)給出所求的最優(yōu)值為m(1,c)=15。17上述算法的主要計(jì)算量在于計(jì)算跳躍點(diǎn)集pi(1in)。由于qi+1=pi+1(wi，vi)，故計(jì)算qi+1需要O(|pi+1|)計(jì)算時(shí)間。合并pi+1和qi+1并清除受控跳躍點(diǎn)也需要O(|pi+1|)計(jì)算時(shí)間。從跳躍點(diǎn)集pi的定義可以看出，pi中的跳躍點(diǎn)相應(yīng)于xi,xn的0/1賦值。因此，pi中跳躍點(diǎn)個(gè)數(shù)不超過2n-i+1。由此可見，算法計(jì)算跳躍點(diǎn)集pi所花費(fèi)的計(jì)算時(shí)間為從而，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O(2n)。當(dāng)所給物品的重量wi(1in)是整數(shù)時(shí)，|pi|c+1，(1in)。在這種

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

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

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

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

22、定給定n n種物品和一個(gè)背包。物品種物品和一個(gè)背包。物品i i的重量是的重量是WiWi，其價(jià)值為，其價(jià)值為ViVi，背包的容量為背包的容量為C C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大品的總價(jià)值最大? ? 23n背包問題：背包問題： 與與0-10-1背包問題類似，所不同的是在選擇物品背包問題類似，所不同的是在選擇物品i i裝入背包時(shí)，裝入背包時(shí)，可以選擇物品可以選擇物品i i的一部分，而不一定要全部裝入背包，的一部分，而不一定要全部裝入背包，1in1in。 這這2 2類問題都具有類問題都具有性質(zhì)，極為相似，但性質(zhì)，極為相似，但背包

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

24、一直地進(jìn)行下去，直到背包裝滿為止。到背包裝滿為止。 具體算法可描述如下頁：具體算法可描述如下頁： 用貪心算法解背包問題的基本步驟：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àn)樵诒嘲鼏栴}，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-10-1背包問題背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該再作出最好選擇

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

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

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

29、25, 25n開始時(shí)，Cr=C=30，V=0，A為唯一活結(jié)點(diǎn)，也是當(dāng)前擴(kuò)展結(jié)點(diǎn)n擴(kuò)展A，先到達(dá)B結(jié)點(diǎn)qCr=Cr-w1=14，V=V+v1=45q此時(shí)A、B為活結(jié)點(diǎn)，B成為當(dāng)前擴(kuò)展結(jié)點(diǎn)q擴(kuò)展B，先到達(dá)DnCrw2，D導(dǎo)致一個(gè)不可行解，回溯到Bq再擴(kuò)展B到達(dá)EnE可行，此時(shí)A、B、E是活結(jié)點(diǎn)，E成為新的擴(kuò)展結(jié)點(diǎn)n擴(kuò)展E，先到達(dá)JqCr45，皆得到一個(gè)可行解x=(0,1,1)，V=50qL不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到Fn再擴(kuò)展F到達(dá)MqM是葉結(jié)點(diǎn)，且2550，不是最優(yōu)解qM不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到FnF沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到Cq再擴(kuò)展C到達(dá)GnCr=30，V=0，活結(jié)點(diǎn)為A、C、G

30、，G為當(dāng)前擴(kuò)展結(jié)點(diǎn)n擴(kuò)展G，先到達(dá)N，N是葉結(jié)點(diǎn)，且2550，不是最優(yōu)解，又N不可擴(kuò)展，返回到Gn再擴(kuò)展G到達(dá)O，O是葉結(jié)點(diǎn)，且050，不是最優(yōu)解，又O不可擴(kuò)展，返回到GnG沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到CqC沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到AnA沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，算法結(jié)束，最優(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解空間：子集樹解空間：子集樹可行性約束函數(shù)：可行性約束函數(shù)：上界

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

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

33、函數(shù)在實(shí)現(xiàn)時(shí)，由函數(shù)BoundBound來計(jì)算在當(dāng)前結(jié)點(diǎn)處的上界。來計(jì)算在當(dāng)前結(jié)點(diǎn)處的上界。它是類它是類KnapKnap的私有成員。的私有成員。KnapKnap的其他成員記錄解空間樹的其他成員記錄解空間樹中的結(jié)點(diǎn)信息，以減少函數(shù)參數(shù)的傳遞以及遞歸調(diào)用時(shí)中的結(jié)點(diǎn)信息，以減少函數(shù)參數(shù)的傳遞以及遞歸調(diào)用時(shí)所需的?？臻g。在解空問樹的當(dāng)前擴(kuò)展結(jié)點(diǎn)處，僅當(dāng)要所需的?？臻g。在解空問樹的當(dāng)前擴(kuò)展結(jié)點(diǎn)處，僅當(dāng)要進(jìn)人右子樹時(shí)才計(jì)算進(jìn)人右子樹時(shí)才計(jì)算L L界函數(shù)界函數(shù)Bound,Bound,以判斷是否可以將以判斷是否可以將右子樹剪去。進(jìn)人左子樹時(shí)不需計(jì)算上界，因?yàn)槠渖辖缬易訕浼羧?。進(jìn)人左子樹時(shí)不需計(jì)算上界，因?yàn)槠渖?/p>

34、界與其父結(jié)點(diǎn)的上界相同。與其父結(jié)點(diǎn)的上界相同。n 在調(diào)用函數(shù)在調(diào)用函數(shù)KnapsackKnapsack之前，需先將各物品依其單位重之前，需先將各物品依其單位重量價(jià)值從大到小排序。為此目的，我們定義了類量價(jià)值從大到小排序。為此目的，我們定義了類ObjectObject。其中，其中，=運(yùn)算符與通常的定義相反，其口的是為了方便運(yùn)算符與通常的定義相反，其口的是為了方便調(diào)用已有的排序算法。在通常情況下，排序算法將待排調(diào)用已有的排序算法。在通常情況下，排序算法將待排序元素從小到大排列。序元素從小到大排列。33templateclass Knapfriend Typep Knapsack(Typep *,T

35、ypew*, Typew ,int );private: Typep Bound(int i); void Backtrack(int i); Typew c;/背包容量背包容量 int n; /物品數(shù)物品數(shù)Typew *w;/物品重量數(shù)組物品重量數(shù)組 Typep *p;/物品價(jià)值數(shù)組物品價(jià)值數(shù)組 Typew cw;/當(dāng)前重量當(dāng)前重量 Typep cp;/當(dāng)前價(jià)值當(dāng)前價(jià)值 Typep bestp;/當(dāng)前最優(yōu)值當(dāng)前最優(yōu)值 Typep *bestx;/當(dāng)前最優(yōu)解當(dāng)前最優(yōu)解 Typep *x;/當(dāng)前解當(dāng)前解; 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)/ 計(jì)算上界計(jì)算上界 Typew cleft = c - cw; / 剩余容量剩余容量 Typep b = cp; / 以物品單位重量價(jià)值遞減序裝入物品以物品單位重量價(jià)值遞減序裝入物品 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）求解目標(biāo)：）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種約束條件的一個(gè)解，或是在滿足約束

40、條件的解中找出在某種意義下的最優(yōu)解。意義下的最優(yōu)解。 （2 2）搜索方式的不同：）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹先的方式搜索解空間樹。 39分支限界法的基本思想分支限界法的基本思想 分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。優(yōu)先的方式搜索問題的解空間樹。 此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找到所并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。需的解或活結(jié)點(diǎn)表為空時(shí)為止。 在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)袃鹤咏Y(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活致非最優(yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)