動(dòng)態(tài)規(guī)劃與回溯法解決0-1背包問題(共9頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上0-1背包動(dòng)態(tài)規(guī)劃解決問題一、問題描述：有n個(gè)物品，它們有各自的重量和價(jià)值，現(xiàn)有給定容量的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？二、總體思路：根據(jù)動(dòng)態(tài)規(guī)劃解題步驟（問題抽象化、建立模型、尋找約束條件、判斷是否滿足最優(yōu)性原理、找大問題與小問題的遞推關(guān)系式、填表、尋找解組成）找出01背包問題的最優(yōu)解以及解組成，然后編寫代碼實(shí)現(xiàn)。三、動(dòng)態(tài)規(guī)劃的原理及過程：number4，capacity7i1234w(重量)3521v(價(jià)值)91074原理：動(dòng)態(tài)規(guī)劃與分治法類似，都是把大問題拆分成小問題，通過尋找大問題與小問題的遞推關(guān)系，解決一個(gè)個(gè)小問題，最終達(dá)到解決原問題的效果

2、。但不同的是，分治法在子問題和子子問題等上被重復(fù)計(jì)算了很多次，而動(dòng)態(tài)規(guī)劃則具有記憶性，通過填寫表把所有已經(jīng)解決的子問題答案紀(jì)錄下來，在新問題里需要用到的子問題可以直接提取，避免了重復(fù)計(jì)算，從而節(jié)約了時(shí)間，所以在問題滿足最優(yōu)性原理之后，用動(dòng)態(tài)規(guī)劃解決問題的核心就在于填表，表填寫完畢，最優(yōu)解也就找到。過程：a)把背包問題抽象化（X1，X2，Xn，其中 Xi 取0或1，表示第 i 個(gè)物品選或不選），Vi表示第 i 個(gè)物品的價(jià)值，Wi表示第 i 個(gè)物品的體積（重量）；b)建立模型，即求max(V1X1+V2X2+VnXn)；c)約束條件，W1X1+W2X2+WnXn (V2X2+V3X3+VnXn)+

3、V1X1；而(V2X2+V3X3+VnXn)+V1X1=(V1X1+V2X2+VnXn)，則有(V2Y2+V3Y3+VnYn)+V1X1(V1X1+V2X2+VnXn)；該式子說明(X1，Y2，Y3，Yn)才是該01背包問題的最優(yōu)解，這與最開始的假設(shè)(X1，X2，Xn)是01背包問題的最優(yōu)解相矛盾，故01背包問題滿足最優(yōu)性原理；f)尋找遞推關(guān)系式，面對當(dāng)前商品有兩種可能性：第一，包的容量比該商品體積小，裝不下，此時(shí)的價(jià)值與前i-1個(gè)的價(jià)值是一樣的，即V(i,j)=V(i-1,j)；第二，還有足夠的容量可以裝該商品，但裝了也不一定達(dá)到當(dāng)前最優(yōu)價(jià)值，所以在裝與不裝之間選擇最優(yōu)的一個(gè)，即V(i,j)

4、=max V(i-1,j)，V(i-1,j-w(i)+v(i) 其中V(i-1,j)表示不裝，V(i-1,j-w(i)+v(i)表示裝了第i個(gè)商品，背包容量減少w(i)但價(jià)值增加了v(i)；由此可以得出遞推關(guān)系式：1)j=w(i) V(i,j)=maxV(i-1,j)，V(i-1,j-w(i)+v(i)number4，capacity7i1234w(重量)3521v(價(jià)值)91074四、構(gòu)造最優(yōu)解：最優(yōu)解的構(gòu)造可根據(jù)C列的數(shù)據(jù)來構(gòu)造最優(yōu)解，構(gòu)造時(shí)從第一個(gè)物品開始。從i=1,j=c即m1c開始。1、對于mij，如果mij=mi+1j，則物品i沒有裝入背包，否則物品i裝入背包； 2、為了確定后繼即

5、物品i+1，應(yīng)該尋找新的j值作為參照。如果物品i已放入背包，則j=j-wi；如果物品i未放入背包，則j=j。3、重復(fù)上述兩步判斷后續(xù)物品i到物品n-1是否放入背包。4、對于物品n，直接通過mnj是否為0來判斷物品n是否放入背包。只要能通過找規(guī)律手工填寫出上面這張表就算理解了01背包的動(dòng)態(tài)規(guī)劃算法。首先要明確這張表是至底向上，從左到右生成的。序號WeightValue123456713947111316202025104711111114173274711111111114144444444從表格中可以看出背包的最大價(jià)值value=20，即當(dāng)X1=1，X2=0，X3=1，X4=1。五、算法測試代

6、碼：#include#include#include#include#include#includeusing namespace std;const int c = 8; /背包的容量const int w = 0,3,5,2,1; /物品的重量，其中0號位置不使用 。 const int v = 0,9,10,7,4; /物品對應(yīng)的待加，0號位置置為空。const int n = sizeof(w)/sizeof(w0) - 1 ; /n為物品的個(gè)數(shù) int xn+1;void package0_1(int m11,const int w,const int v,const int n)/

7、n代表物品的個(gè)數(shù) /采用從底到頂?shù)捻樞騺碓O(shè)置mij的值 /首先放wn for(int j = 0; j = c; j+) if(j = 1; i-) for(int j = 0; j = c; j+) if(j wi) mij = mi+1j;/如果j mi+1j-wi + vi? mi+1j : mi+1j-wi + vi; void answer(int m11,const int n) int j = c; int i; for(i = 1; i = n-1; i+) if(mij = mi+1j) xi = 0; else xi = 1; j = j - wi; xn = mij ?

8、1 : 0; int main() int m611=0; package0_1(m,w,v,n); for(int i = 0; i = 5; i+) for(int j = 0; j = 10; j+) printf(%2d ,mij); cout endl; answer(m,n); cout The best answer is:n; for(int i = 1; i = 5; i+) cout xi ; system(pause); return 0;0-1背包回溯法解決問題一、問題描述：有n個(gè)物品，它們有各自的重量和價(jià)值，現(xiàn)有給定容量的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和

9、？二、總體思路：01背包屬于找最優(yōu)解問題，用回溯法需要構(gòu)造解的子集樹。在搜索狀態(tài)空間樹時(shí)，只要左子節(jié)點(diǎn)是可一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入其左子樹。對于右子樹時(shí)，先計(jì)算上界函數(shù)，以判斷是否將其減去。上界函數(shù)bound():當(dāng)前價(jià)值cw+剩余容量可容納的最大價(jià)值=當(dāng)前最優(yōu)價(jià)值bestp。為了更好地計(jì)算和運(yùn)用上界函數(shù)剪枝，選擇先將物品按照其單位重量價(jià)值從大到小排序，此后就按照順序考慮各個(gè)物品。三、回溯法實(shí)現(xiàn)的過程：number4，capacity7i1234w(重量)3521v(價(jià)值)91074根據(jù)問題的解空間，對于n=4時(shí)的0-1背包問題，可用一棵完全二叉樹表示其解空間，如下圖所示。回溯過程：從根節(jié)點(diǎn)A

10、開始回溯，節(jié)點(diǎn)A是當(dāng)前的唯一的活節(jié)點(diǎn)，在這個(gè)縱深方向先進(jìn)入A的左子樹B或者右子樹C。假設(shè)先選擇節(jié)點(diǎn)B，此時(shí)，節(jié)點(diǎn)B成為當(dāng)前的活節(jié)點(diǎn)，節(jié)點(diǎn)B成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。節(jié)點(diǎn)A到B選擇w1=3,節(jié)點(diǎn)B背包剩余容量r=4,價(jià)值v=9,節(jié)點(diǎn)B到節(jié)點(diǎn)D，由于選擇w2=5,此時(shí)背包容量r=4,背包容量不夠，因而不可行，利用剪枝函數(shù)，減去以D為根節(jié)點(diǎn)的子樹；然后回溯到B的右節(jié)點(diǎn)E，此時(shí)，E節(jié)點(diǎn)的剩余容量r=4，v=9, 選擇w3=2,符合要求，節(jié)點(diǎn)E成為當(dāng)前的擴(kuò)展節(jié)點(diǎn)，進(jìn)入節(jié)點(diǎn)J,此時(shí)，節(jié)點(diǎn)J的剩余容量r=2，v=16，選擇w4=1,符合要求，到葉子節(jié)點(diǎn)T，此時(shí)，節(jié)點(diǎn)T的剩余容量r=1，v=20；因此得到一個(gè)可行解，

11、即x=(1,0,1,1)，此時(shí)節(jié)點(diǎn)T成為一個(gè)死結(jié)點(diǎn)，回溯到節(jié)點(diǎn)U，得到一個(gè)可行解v=16,即x=(1,0,1,0),節(jié)點(diǎn)U成為死結(jié)點(diǎn)，回溯到節(jié)點(diǎn)E,進(jìn)入右子樹，節(jié)點(diǎn)K的剩余容量r=4,v=9,選擇w4=1，符合要求，到達(dá)節(jié)點(diǎn)V，v=13,得到一個(gè)可行解x=(1,0,0,1),節(jié)點(diǎn)V成為死結(jié)點(diǎn)，回溯到節(jié)點(diǎn)K，到達(dá)葉子結(jié)點(diǎn)W，v=9得到一個(gè)可行解x=(1,0,0,0)。按此方式繼續(xù)搜索整個(gè)解的空間。搜索結(jié)束后找到的最好解是0-1背包問題的最優(yōu)解。五、算法測試代碼：#include #include int n;/物品數(shù)量double c;/背包容量double v100;/各個(gè)物品的價(jià)值doubl

12、e w100;/各個(gè)物品的重量double cw = 0.0;/當(dāng)前背包重量double cp = 0.0;/當(dāng)前背包中物品價(jià)值double bestp = 0.0;/當(dāng)前最優(yōu)價(jià)值double perp100;/單位物品價(jià)值排序后int order100;/物品編號int put100;/設(shè)置是否裝入/按單位價(jià)值排序void knapsack()int i,j;int temporder = 0;double temp = 0.0;for(i=1;i=n;i+)perpi=vi/wi;for(i=1;i=n-1;i+)for(j=i+1;j=n;j+)if(perpin)bestp = cp;return;if(cw+wibestp)/符合條件搜索右子數(shù)backtrack(i+1);/計(jì)算上界函數(shù)double bound(int i)double leftw= c-cw;double b = cp;while(i=n&wi=leftw)leftw-=wi;b+=vi;i+;if(i=n)b+=vi/wi*leftw;return b;int main()int i;printf(請輸入物品的數(shù)量和容量：);scanf(%d %lf,&n,&c);printf(請輸入物品的重量和價(jià)值：);for(i=1;i=n;i+)