1、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ī)劃的原理及過程：number =4, capacity = 7ii234w（重里）352iv（價(jià)彳t ）9i074原理：動(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）把背包問題抽象化 （Xi, X2,，Xn,其中Xi取0或1 ,表示第i個(gè)物品選或不選）， Vi表示第i個(gè)物品的價(jià)值， Wi表示第i個(gè)物品的體積（重量）；b）建立模型，即求 max（V iXi+V2X2+ - +VnXn）;c）約束條件，WiXi+W 2X2+WnXn<capacity ;d）

3、定義V（i,j）：當(dāng)前背包容量j,前i個(gè)物品最佳組合對(duì)應(yīng)的價(jià)值；e）最優(yōu)性原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)，最優(yōu)性原理是指多階段決策過程的最優(yōu)決策序列具有這樣的性質(zhì)：不論初始狀態(tài)和初始決策如何，對(duì)于前面決策所造成的某一狀態(tài)而言，其后各階段的決策序列必須構(gòu)成最優(yōu)策略判斷該問題是否滿足最優(yōu)性原理，采用反證法證明：假設(shè)（Xi, X2,，Xn）是0i背包問題的最優(yōu)解，則有（X2, X3,，Xn）是其子問題 的最優(yōu)解，假設(shè)（丫2 , 丫3，Yn）是上述問題的子問題最優(yōu)解，則理應(yīng)有 （V2Y2+V3Y3+ - +VnYn）+V iXi > （V 2X2+V3X3+VnXn）+V iXi；而(V2X2+V3X3+

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

5、個(gè)，即 V(i,j)=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)=V(i-1,j)2) j>=w(i) V(i,j)=max V(i-1,j), V(i-1,j-w(i)+v(i)number =4, capacity = 7i1234w(重里)3521v（價(jià)彳1 ）91074四、構(gòu)造最優(yōu)解：最優(yōu)解的構(gòu)造可根據(jù)C列的數(shù)據(jù)來構(gòu)造最優(yōu)解，構(gòu)造時(shí)從第一個(gè)物品開始。從i=1尸c即m1c開始

6、。1、對(duì)于mij,如果mij=mi+1j,則物品i沒有裝入背包，否則物品i裝入背包；2、為了確定后繼即物品i+1 ,應(yīng)該尋找新的j值作為參照。如果物品i已放入背包， 則j=j-wi；如果物品i未放入背包，則j=j。3、重復(fù)上述兩步判斷后續(xù)物品i到物品n-1是否放入背包。4、對(duì)于物品n,直接通過 mnj是否為0來判斷物品n是否放入背包。01背包的動(dòng)態(tài)規(guī)劃算法。只要能通過找規(guī)律手工填寫出上面這張表就算理解了 首先要明確這張表是至底向上，從左到右生成的。序號(hào)WeightValue1234567139471113162025104711111114173274711111111114144144444

7、從表格中可以看出背包的最大價(jià)值value=20 ,即當(dāng)X1=1 , X2=0 , X3=1 , X4=1 。五、算法測(cè)試代碼:#include<stdio.h>#include<stdlib.h>#include<iostream>#include<queue>#include<climits>#include<cstring>using namespace std;constint c = 8;/背包的容量constint w口 = 0,3,5,2,1;/物品的重量，其中 0號(hào)位置不使用。constint v = 0,9

8、,10,7,4;/ 物品對(duì)應(yīng)的待加，0號(hào)位置置為空。constint n = sizeof(w)/sizeof(w0) - 1 ; /n 為物品的個(gè)數(shù)int xn+1;void package0_1(int m11,constint w,constint v,constint n)/n代表物品的個(gè)數(shù)/采用從底到頂?shù)捻樞騺碓O(shè)置mij的值首先放wnfor(int j = 0; j <= c; j+)if(j < wn) mnj = 0;/j小于wn,所對(duì)應(yīng)的值設(shè)為0,否則就為可以放置else mnj = vn;/對(duì)剩下的n-1個(gè)物品進(jìn)行放置。inti;for(i = n-1; i>

9、;= 1; i-)for(int j = 0; j <= c; j+)if(j < wi)mij = mi+1j;/ 如果j < wi則，當(dāng)前位置就不能放置，它等于上一個(gè)位置的值。/否則，就比較到底是放置之后的值大，還是不放置的值大，選擇其中較大者。elsemij = mi+1j > mi+1j-wi + vi? mi+1j : mi+1j-wi + vi;void answer(int m11,constint n)int j = c;inti;for(i = 1; i<= n-1; i+)if(mij = mi+1j) xi = 0;elsexi = 1;j

10、= j - wi;)xn = mij ? 1 : 0;)int main()(int m611=0;package0_1(m,w,v,n);for(inti = 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(inti = 1; i<= 5; i+)cout<< xi << ""system

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

12、溯法實(shí)現(xiàn)的過程：number =4, capacity = 7i1234w(重里)3521v（價(jià)彳1 ）91074根據(jù)問題的解空間，對(duì)于n=4時(shí)的0-1背包問題，可用一棵完全二叉樹表示其解空間，如下圖所示。回溯過程：從根節(jié)點(diǎn)A開始回溯，節(jié)點(diǎn)A是當(dāng)前的唯一的活節(jié)點(diǎn)，在這個(gè)縱深方向先進(jìn)入 A的左子樹B或者右子樹Co假設(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選才W 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

13、,此時(shí)，E節(jié)點(diǎn)的剩余容量r=4 , v=9,選才w 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 ,選才w w4=1,符合要求，到葉子節(jié)點(diǎn) T,此時(shí)，節(jié)點(diǎn) T的剩余容量r=1 , v=20 ;因此得到一個(gè)可行解，即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,選才w 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á)葉

14、子結(jié)點(diǎn) W, v=9得到一個(gè)可行解 x=(1,0,0,0)。按此方式繼續(xù)搜索整 個(gè)解的空間。搜索結(jié)束后找到的最好解是0-1背包問題的最優(yōu)解。五、算法測(cè)試代碼：#include <stdio.h>#include <conio.h>int n;物品數(shù)量double c;背包容量double v100;/各個(gè)物品的價(jià)值double 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 order10

15、0;/ 物品編號(hào)int put100;/ 設(shè)置是否裝入/按單位價(jià)值排序void knapsack() inti,j;inttemporder = 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(perpi<perpj)/冒泡排序 perp,order,sortv,sortwtemp = perpi; perpi=perpi; perpj=temp;temporder=orderi;orderi=orderj;orderj=temporder

16、;temp = vi;vi=vj;vj=temp;temp=wi;wi=wj;wj=temp;)/回溯函數(shù)void backtrack(inti)(double bound(inti);if(i>n)(bestp = cp;return;)if(cw+wi<=c)(cw+=wi;cp+=vi;puti=1;backtrack(i+1);cw-=wi;cp-=vi;)if(bound(i+1)>bestp)符合條件搜索右子數(shù)backtrack(i+1);)/計(jì)算上界函數(shù)double bound(inti)(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()(inti;printf("請(qǐng)輸入物品的數(shù)量和容量：");scanf("%d %lf",&n,&c);printf("請(qǐng)輸入物品的重量和價(jià)值：");for(i=1;i<=n;i+)(printf(" 第個(gè)物品的重量："