1、動態(tài)規(guī)劃與回溯法解決0-1背包問題0-1背包動態(tài)規(guī)劃解決問題一、問題描述：有n個物品，它們有各自的重量和價值，現(xiàn)有給定容量的背包，如何讓背包里裝入的物品具有最大的價值總和？二、總體思路：根據(jù)動態(tài)規(guī)劃解題步驟（問題抽象化、建立模型、尋找約束條件、判斷是否滿足最優(yōu)性原理、找大問題與小問題的遞推關(guān)系式、填表、尋找解組成）找出01背包問題的最優(yōu)解以及解組成，然后編寫代碼實現(xiàn)。三、動態(tài)規(guī)劃的原理及過程：number=4,capacity=7i34w（重量）3521v（價值）91074原理:動態(tài)規(guī)劃與分治法類似，都是把大問題拆分成小問題，通過尋找大問題與小問題的遞推關(guān)系，解決一個個小問題，最終達到解決原問

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

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

4、 TOC o 1-5 h z 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個商品，背包容量減少w(i)但價值增加了v(i);由此可以得出遞推關(guān)系式：j=w(i)V(i,j)=maxV(i-1,j)，V(i-1,j-w(i)+v(i)number=4,capacity=7i1234w（重量）3521v（價值）91074四、構(gòu)造最優(yōu)解：最優(yōu)解的構(gòu)造可根據(jù)C列的數(shù)據(jù)來構(gòu)造最優(yōu)解，構(gòu)造時從第一個物品開始。從i=1,j=c即m1c開始。1、對于mij,如果mij=mi+1j,則物品i沒有裝入背包，否則物品i裝入背包；為了

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

6、#include#include#include#include#include#includeusingnamespacestd;constintc=8;/背包的/物品/物品的重量，其中0號位置不使用容量constintw=0,3,5,2,1；constintv=0,9,10,7,4;對應(yīng)的待加，0號位置置為空constintn=sizeof(w)/sizeof(w0)-1;n為物品的個數(shù)intxn+1;voidpackage0_1(intm11,constintw,constintv,constintn)n代表物品的個數(shù)/采用從底到頂?shù)捻樞騺碓O(shè)置mij的值/首先放wnfor(intj=0;

7、j=c;j+)if(j=1;i-)for(intj=0;j=c;j+)if(jwi)mij=mi+1j;如果jmi+1j-wi+vi?mi+1j:mi+1j-wi+vi;voidanswer(intm11,constintn)intj=c;inti;for(i=1;i=n-1;i+)if(mij=mi+1j)xi=0;elsexi=1;j=j-wi;xn=mij?1:0;intmain()intm611=0;packageO_1(m,w,v,n);for(inti=0;i=5;i+)for(intj=0;j=10;j+)printf(%2d,mij);coutendl;answer(m,n);

8、coutThebestansweris:n;for(inti=1;i=5;i+)coutxi;system(pause);return0;0-1背包回溯法解決問題問題描述:有n個物品，它們有各自的重量和價值，現(xiàn)有給定容量的背包，如何讓背包里裝入的物品具有最大的價值總和？總體思路：01背包屬于找最優(yōu)解問題，用回溯法需要構(gòu)造解的子集樹。在搜索狀態(tài)空間樹時，只要左子節(jié)點是可一個可行結(jié)點，搜索就進入其左子樹。對于右子樹時，先計算上界函數(shù)，以判斷是否將其減去。上界函數(shù)bound():當(dāng)前價值cw+剩余容量可容納的最大價值=當(dāng)前最優(yōu)價值bestp。為了更好地計算和運用上界函數(shù)剪枝，選擇先將物品按照其單位重

9、量價值從大到小排序，此后就按照順序考慮各個物品。三、回溯法實現(xiàn)的過程：number=4,capacity=7i1234w（重量）3521v（價值）91074根據(jù)問題的解空間，對于n=4時的0-1背包問題，可用一棵完全二叉樹表示其解空間，如下圖所示。B!0D)E)1/0K：1/ OO 1 o1 00(P：Q） （R；：s(T)SIX) *YZ)回溯過程：從根節(jié)點A開始回溯，節(jié)點A是當(dāng)前的唯一的活節(jié)點,在這個縱深方向先進入A的左子樹B或者右子樹Co假設(shè)先選擇節(jié)點B,此時，節(jié)點B成為當(dāng)前的活節(jié)點，節(jié)點B成為當(dāng)前擴展節(jié)點。節(jié)點A到B選擇w仁3,節(jié)點B背包剩余容量r=4,價值v=9,節(jié)點B到節(jié)點D,由于

10、選擇w2=5,此時背包容量r=4,背包容量不夠，因而不可行，利用剪枝函數(shù)，減去以D為根節(jié)點的子樹；然后回溯到B的右節(jié)點E,此時，E節(jié)點的剩余容量r=4,v=9,選擇w3=2,符合要求，節(jié)點E成為當(dāng)前的擴展節(jié)點，進入節(jié)點J,此時，節(jié)點J的剩余容量r=2,v=16,選擇w4=1,符合要求，到葉子節(jié)點T,此時，節(jié)點T的剩余容量r=1,v=20;因此得到一個可行解，即x=(1,0,1,1),此時節(jié)點T成為一個死結(jié)點，回溯到節(jié)點U,得到一個可行解v=16，即x=(1,0,1,0),節(jié)點U成為死結(jié)點，回溯到節(jié)點E,進入右子樹，節(jié)點K的剩余容量r=4,v=9,選擇w4=1,符合要求，到達節(jié)點V,v=13,得

11、到一個可行解x=(1,0,0,1)，節(jié)點V成為死結(jié)點，回溯到節(jié)點K,到達葉子結(jié)點W,v=9得到一個可行解x=(1,0,0,0)。按此方式繼續(xù)搜索整個解的空間。搜索結(jié)束后找到的最好解是0-1背包問題的最優(yōu)解。五、算法測試代碼：#include1#ineludevconio.hintn;物品數(shù)量doublec;背包容量doublev100;各個物品的價值doublew100;各個物品的重量doublecw=0.0;/當(dāng)前背包重量doublecp=0.0;/當(dāng)前背包中物品價值doublebestp=0.0;/當(dāng)前最優(yōu)價值doubleperp100;單位物品價值排序后intorder100;/物品編號

12、intput100;/設(shè)置是否裝入1按單位價值排序voidknapsack()1inti,j;inttemporder=0;doubletemp=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);/計算上界函數(shù)doublebound(inti)doubleleftw=c-cw;doubleb=cp;while(i=n&wiv=leftw)leftw-=wi;b+=vi;i+;if(i=n)b+=vi/wi*leftw;returnb;intmain()(inti;printff請輸入物品的數(shù)量和容量：);scanf(%d%lf,&n,&c);printf(請輸入物品的重量和價值：)；for(i=1;i=n;i+)