背包問(wèn)題詳解.ppt

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問(wèn)題陳述：?jiǎn)栴}陳述：n給定給定n n種物品和一背包。物品種物品和一背包。物品i i的重量是的重量是wiwi，其價(jià)值為，其價(jià)值為vivi，背包的，背包的容量為容量為c c。問(wèn)應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品。問(wèn)應(yīng)如何選擇裝入背包

2、中的物品，使得裝入背包中物品的總價(jià)值最大？的總價(jià)值最大？n在選擇裝入背包的物品時(shí)，對(duì)每種物品在選擇裝入背包的物品時(shí)，對(duì)每種物品i i只有兩種選擇，即裝入背只有兩種選擇，即裝入背包或不裝入背包。不能將物品包或不裝入背包。不能將物品i i裝入背包多次，也不能只裝入部分裝入背包多次，也不能只裝入部分的物品的物品i i。因此，該問(wèn)題稱為。因此，該問(wèn)題稱為0-10-1背包問(wèn)題。背包問(wèn)題。nn解題思路：解題思路：n此問(wèn)題可轉(zhuǎn)化為：給定此問(wè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ī)劃問(wèn)題：整數(shù)規(guī)劃問(wèn)題：n max max vixivixin s.ts.t. . wixicwixic，n xi0 xi0，11，1in1inn可用動(dòng)態(tài)規(guī)劃算法求解?？捎脛?dòng)態(tài)規(guī)劃算法求解。5其他類型背包問(wèn)題n完全背包問(wèn)題完全背包問(wèn)題(0/1)(0/1)：q有有n n種物品和一個(gè)容量為種物品和一個(gè)容量為v v的背包，每種物品都有的背包，每種物品都有無(wú)無(wú)限限件可用。第件可用。第i i種物品的費(fèi)用是種物品的費(fèi)用是cici ，價(jià)值是，

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

5、kxvmaxnkixjxwknikkk,1 , 0的最優(yōu)值為的最優(yōu)值為m(i，j)，即，即m(i，j)是背包容量為是背包容量為j，可選擇物品為，可選擇物品為i，i+1，n時(shí)時(shí)0-1背包問(wèn)題的最優(yōu)值。由背包問(wèn)題的最優(yōu)值。由0-1背包問(wèn)題的最優(yōu)子背包問(wèn)題的最優(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背包問(wèn)題可以看作是決策一個(gè)序列背包問(wèn)題可以看作是決策一個(gè)序列(x1, x2, , xn)，對(duì)任對(duì)任一變量一變量xi的決策是決定的決策是決定xi=1還是還是xi=0。在對(duì)在對(duì)xi-1決策后，已確定了決策后，已確定了(x1, , xi-1)，在決策在決策xi時(shí)，問(wèn)題處于下列兩種狀態(tài)之一：時(shí)，問(wèn)題處于下列兩種狀態(tài)之一：（1）背包容量不足以裝入物品）背包容量不足以裝入物品i，則，則xi=0，背包不增加價(jià)值；背包不增加價(jià)值；（2）背包容量可

7、以裝入物品）背包容量可以裝入物品i，則，則xi=1，背包的價(jià)值增加了背包的價(jià)值增加了vi。 這兩種情況下背包價(jià)值的最大者應(yīng)該是這兩種情況下背包價(jià)值的最大者應(yīng)該是對(duì)對(duì)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)的遞歸式容易證明，在一般情況下，對(duì)每一個(gè)確定的的遞歸式容易證明，在一

12、般情況下，對(duì)每一個(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)唯一確定。如圖所示。對(duì)每一個(gè)確定的對(duì)每一個(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)。由此可見(jiàn)，在遞歸地由表由此可見(jià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ù)不超過(guò)2n-i+1。由此可見(jiàn)，算法計(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é)著重討論可以用貪心算法求解的問(wèn)題的一般特征。本節(jié)著重討論可以用貪心算法求解的問(wèn)題的一般特征。 對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢以及能否得到問(wèn)題的最優(yōu)解呢? ?這個(gè)問(wèn)題很難給予肯定的回答。這個(gè)問(wèn)題很難給予肯定的回答。 但是，從許多可以用貪心算法求解的問(wèn)題中看到這類問(wèn)題一般但是，從許多可以用貪心算法求解的問(wèn)題中看到這類問(wèn)題一般具有具有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ì) 所謂所謂是指所求問(wèn)題的是指所求問(wèn)題的可以可以通過(guò)一系列通過(guò)一系列的選擇，即貪心選擇來(lái)達(dá)到。這是的選擇，即貪心選擇來(lái)達(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ī)劃算法通常以的方式解各子問(wèn)題，的方式解各子問(wèn)題，而貪心算法則通常以而貪心算法則通常以的方式進(jìn)行，以迭代的方的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)式作出相繼的貪心選擇，每作一次貪心選擇就

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

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

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

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

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

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

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

28、量：回溯法希望一個(gè)問(wèn)題的解能夠表示成一個(gè)n元式(x1,x2,xn)的形式。顯約束：對(duì)分量xi的取值限定。隱約束：為滿足問(wèn)題的解而對(duì)不同分量之間施加的約束。解空間：對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。注意：同一個(gè)問(wèn)題可以有多種表示，有些表示方法更簡(jiǎn)單，注意：同一個(gè)問(wèn)題可以有多種表示，有些表示方法更簡(jiǎn)單，所需表示的狀態(tài)空間更?。ù鎯?chǔ)量少，搜索方法簡(jiǎn)單）。所需表示的狀態(tài)空間更小（存儲(chǔ)量少，搜索方法簡(jiǎn)單）。n=3時(shí)的時(shí)的0-1背包問(wèn)題用完全二叉樹表示的解空間背包問(wèn)題用完全二叉樹表示的解空間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沒(méi)有可擴(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沒(méi)有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到cqc沒(méi)有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到ana沒(méi)有可擴(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背包問(wèn)題是一個(gè)子集選取問(wèn)題，背包問(wèn)題是一個(gè)子集選取問(wèn)題，適合于用子集樹表示適合于用子集樹表示01背包問(wèn)題的解空間。背包問(wèn)題的解空間。在搜索解空間樹是，只要其左兒子節(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)入右子樹搜索。否則將右子樹剪去。否則將右子樹剪去。 例如，對(duì)于例如，對(duì)于0-1背包問(wèn)題的一個(gè)實(shí)例，背包問(wèn)題的一個(gè)實(shí)例，n=4,c=7, p=9,10,7,4，w=3,5,2,1。這。這4個(gè)物品的單位重量?jī)r(jià)值分別為個(gè)

32、物品的單位重量?jī)r(jià)值分別為3,2,3.5,4。以物品單位。以物品單位重量?jī)r(jià)值的遞減序裝入物品。首先裝入物品重量?jī)r(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è)上界。因此，對(duì)于這個(gè)實(shí)例，最優(yōu)值不超過(guò)證明其價(jià)值是最優(yōu)值的一個(gè)上界。因此，對(duì)于這個(gè)實(shí)例，最優(yōu)值不超過(guò)22。32n在實(shí)現(xiàn)時(shí)，由

33、函數(shù)在實(shí)現(xiàn)時(shí)，由函數(shù)boundbound來(lái)計(jì)算在當(dāng)前結(jié)點(diǎn)處的上界。來(lái)計(jì)算在當(dāng)前結(jié)點(diǎn)處的上界。它是類它是類knapknap的私有成員。的私有成員。knapknap的其他成員記錄解空間樹的其他成員記錄解空間樹中的結(jié)點(diǎn)信息，以減少函數(shù)參數(shù)的傳遞以及遞歸調(diào)用時(shí)中的結(jié)點(diǎn)信息，以減少函數(shù)參數(shù)的傳遞以及遞歸調(diào)用時(shí)所需的棧空間。在解空問(wèn)樹的當(dāng)前擴(kuò)展結(jié)點(diǎn)處，僅當(dāng)要所需的?？臻g。在解空問(wèn)樹的當(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)槠渖辖缬易訕浼羧ァ＿M(jìn)人左子樹時(shí)不需計(jì)算上界，因?yàn)槠渖?/p>

34、界與其父結(jié)點(diǎn)的上界相同。與其父結(jié)點(diǎn)的上界相同。n 在調(diào)用函數(shù)在調(diào)用函數(shù)knapsackknapsack之前，需先將各物品依其單位重之前，需先將各物品依其單位重量?jī)r(jià)值從大到小排序。為此目的，我們定義了類量?jī)r(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; / 以物品單位重量?jī)r(jià)值遞減序裝入物品以物品單位重量?jī)r(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)先的方式搜索問(wèn)題的解空間樹。優(yōu)先的方式搜索問(wèn)題的解空間樹。 此后，從活結(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ò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(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)。活結(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)