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

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

3、定義V（i,j）：當前背包容量j,前i個物品最佳組合對應的價值；e）最優性原理是動態規劃的基礎，最優性原理是指多階段決策過程的最優決策序列具有這樣的性質：不論初始狀態和初始決策如何，對于前面決策所造成的某一狀態而言，其后各階段的決策序列必須構成最優策略判斷該問題是否滿足最優性原理，采用反證法證明：假設（Xi, X2,，Xn）是0i背包問題的最優解，則有（X2, X3,，Xn）是其子問題 的最優解，假設（丫2 , 丫3，Yn）是上述問題的子問題最優解，則理應有 （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背包問題的最優解，這與最開始的假設 (X1, X2,，Xn)是01背包問題的最優解相矛盾，故 01背包問題滿足最優性原理；f)尋找遞推關系式，面對當前商品有兩種可能性：第一，包的容量比該商品體積小，裝不下，此時的價值與前i-1個的價值是一樣的，即 V(i,j)=V(i-1,j);第二，還有足夠的容量可以裝該商品，但裝了也不一定達到當前最優價值，所以在裝與不裝之間選擇最優的一

5、個，即 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個商品，背包容量減少w(i)但價值增加了 v(i);由此可以得出遞推關系式：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（價彳1 ）91074四、構造最優解：最優解的構造可根據C列的數據來構造最優解，構造時從第一個物品開始。從i=1尸c即m1c開始

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

7、從表格中可以看出背包的最大價值value=20 ,即當X1=1 , X2=0 , X3=1 , X4=1 。五、算法測試代碼:#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號位置不使用。constint v = 0,9

8、,10,7,4;/ 物品對應的待加，0號位置置為空。constint n = sizeof(w)/sizeof(w0) - 1 ; /n 為物品的個數int xn+1;void package0_1(int m11,constint w,constint v,constint n)/n代表物品的個數/采用從底到頂的順序來設置mij的值首先放wnfor(int j = 0; j <= c; j+)if(j < wn) mnj = 0;/j小于wn,所對應的值設為0,否則就為可以放置else mnj = vn;/對剩下的n-1個物品進行放置。inti;for(i = n-1; i>

9、;= 1; i-)for(int j = 0; j <= c; j+)if(j < wi)mij = mi+1j;/ 如果j < wi則，當前位置就不能放置，它等于上一個位置的值。/否則，就比較到底是放置之后的值大，還是不放置的值大，選擇其中較大者。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個物品，它們有各自的重量和價值，現有給定容量的背包，如何讓背包 里裝入的物品具有最大的價值總和？、總體思路：|01背包屬于找最優解問題，用回溯法需要構造解的子集樹。在搜索狀態空間樹時，只 要左子節點是可一個可行結點，搜索就進入其左子樹。對于右子樹時，先計算上界函 數，以判斷是否將其減去。上界函數bound():當前價值cw+剩余容量可容納的最大價值 <=當前最優價值bestp。 為了更好地計算和運用上界函數剪枝，選擇先將物品按照其單位重量價值從大到小排 序，此后就按照順序考慮各個物品。三、回

12、溯法實現的過程：number =4, capacity = 7i1234w(重里)3521v（價彳1 ）91074根據問題的解空間，對于n=4時的0-1背包問題，可用一棵完全二叉樹表示其解空間，如下圖所示?；厮葸^程：從根節點A開始回溯，節點A是當前的唯一的活節點，在這個縱深方向先進入 A的左子樹B或者右子樹Co假設先選擇節點 B,此時，節點B成為當前的活節點，節點 B成為當前擴展 節點。節點A到B選才W w1=3,節點B背包剩余容量r=4,價值v=9,節點B到節點D,由于選擇w2=5, 此時背包容量r=4,背包容量不夠，因而不可行，利用剪枝函數，減去以D為根節點的子樹； 然后回溯到B的右節點E

13、,此時，E節點的剩余容量r=4 , v=9,選才w w3=2,符合要求，節點 E成為當前的擴展節點，進入節點J,此時，節點J的剩余容量r=2 , v=16 ,選才w w4=1,符合要求，到葉子節點 T,此時，節點 T的剩余容量r=1 , v=20 ;因此得到一個可行解，即x=(1,0,1,1),此時節點 T成為一個死結點，回溯到節點 U ,得到一個可行解v=16,即x=(1,0,1,0),節點U成為死結點，回溯到節點E,進入右子樹，節點 K的剩余容量r=4,v=9,選才w w4=1，符合要求，到達節點V,v=13，得到一個可行解 x=(1,0,0,1),節點V成為死結點， 回溯到節點K,到達葉

14、子結點 W, v=9得到一個可行解 x=(1,0,0,0)。按此方式繼續搜索整 個解的空間。搜索結束后找到的最好解是0-1背包問題的最優解。五、算法測試代碼：#include <stdio.h>#include <conio.h>int n;物品數量double c;背包容量double v100;/各個物品的價值double w100;各個物品的重量double cw = 0.0;/當前背包重量double cp = 0.0;/ 當前背包中物品價值double bestp = 0.0;/當前最優價值double perp100;單位物品價值排序后int order10

15、0;/ 物品編號int put100;/ 設置是否裝入/按單位價值排序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;)/回溯函數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)符合條件搜索右子數backtrack(i+1);)/計算上界函數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("請輸入物品的數量和容量：");scanf("%d %lf",&n,&c);printf("請輸入物品的重量和價值：");for(i=1;i<=n;i+)(printf(" 第個物品的重量："