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

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

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

3、即求 max(V 1X1+V 2X2+ +VnXn) ；c) 約束條件，W1X1+W 2X2+ +WnXn(V 2X2+V 3X3+ +VnXn)+V 1X1；而(V 2X2+V 3X3+ +VnXn)+V 1X1=(V 1X1+V 2X 2+ +VnXn) ，則有(V 2Y2+V 3Y3+ +VnYn)+V 1X1 (V 1X1+V 2 X2+ +VnXn) ；該式子說明 (X 1，Y2 ，Y3，Yn) 才是 該 01 背包問題的最優(yōu)解，這與最開始的假設 (X 1，X2，Xn) 是 01 背包問題的最優(yōu)解相矛 盾，故 01 背包問題滿足最優(yōu)性原理；f) 尋找遞推關系式， 面對當前商品有兩種可

4、 能性：第一，包的容量比該商品體積小， 裝不 下，此時的價值與前 i-1 個的價值是一樣的，即 V(i,j)=V(i-1,j) ；第二，還有足夠的容量可以裝該商品， 但裝了也不一定達到當前最優(yōu)價值， 所以在裝與 不裝之間選擇最優(yōu)的一個，即 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)=max V(i-1,j) ， V(i-1,j-w(i)+v(i) numbe

5、r 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 裝入背包；2 、為了確定后繼即物品 i+1 ，應該尋找新 的 j 值作為參照。如果物品 i 已放入背包，則 j=j-wi ；如果物品 i 未放入背包，則 j=j 。3 、重復上述兩步判斷后續(xù)物品 i 到物品 n-1 是否放入背包。4 、對于物品 n ，直接通過 mnj 是否為 0 來判斷物品 n

6、是否放入背包。只要能通過找規(guī)律手工填寫出上面這張表就算 理解了 01 背包的動態(tài)規(guī)劃算法。首先要明確這張表是至底向上，從左到右生成 的。序 號WeightValue123456713947111316202025104711111114173274711111111114144444444從表格中可以看出背包的最大價值 value=20 即當 X1=1 ， X2=0 ，X3=1 ，X4=1 。五、算法測試代碼： #include #include #include #include #include #include using namespace std;/ 背包的/ 物品/ 物品const

7、 int c = 8; 容量的重量，其中 0 號位置不使用const int w = 0,3,5,2,1;const int v = 0,9,10,7,4;對應的待加， 0 號位置置為空 const int n = sizeof(w)/sizeof(w0) - 1 ;/n 為物品的個數(shù) int xn+1;void package0_1(int m11,const intw,const int v,const int n)/n代表物品的個數(shù)/采用從底到頂?shù)捻樞騺碓O置 mij 的值/首先放 wnfor(int j = 0; j = c; j+)if(j = 1; i-)for(int j = 0;

8、 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 ? 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+

9、) 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 個物品，它們有各自的重量和價值，現(xiàn)有給定容量的背包，如何讓背 包里裝入的物品具有最大的價值總和？二、總體思路：01 背包屬于找最優(yōu)解問題，用回溯法需要構(gòu) 造解的子集樹。在搜索狀態(tài)空間樹時，只要 左子節(jié)點是可一個可行結(jié)點，搜索就進入其 左子樹。對于右子樹時，先計算上界函數(shù)，以判斷是否將其減去。上界函

10、數(shù) bound(): 當前價值 cw+ 剩余容量 可容納的最大價值 = 當前最優(yōu)價值 bestp 。 為了更好地計算和運用上界函數(shù)剪枝，選擇 先將物品按照其單位重量價值從大到小排 序，此后就按照順序考慮各個物品。三、回溯法實現(xiàn)的過程：number 4 ，capacity 7i1234w( 重3521量)v( 價91074值)根據(jù)問題的解空間，對于 n=4 時的 0-1 背包問 題，可用一棵完全二叉樹表示其解空間， 如下圖 所示?；厮葸^程：從根節(jié)點 A 開始回溯，節(jié)點 A 是當前的唯一的 活節(jié)點，在這個縱深方向先進入 A 的左子樹 B 或者右子樹 C。假設先選擇節(jié)點 B，此時，節(jié)點 B 成為當前

11、的活節(jié)點，節(jié)點 B 成為當前擴展節(jié) 點。節(jié)點 A 到 B 選擇 w1=3, 節(jié)點 B 背包剩余容量 r=4, 價值 v=9, 節(jié)點 B 到節(jié)點 D ，由于選擇 w2=5, 此時背包容量 r=4, 背包容量不夠，因而 不可行，利用剪枝函數(shù)，減去以 D 為根節(jié)點的 子樹；然后回溯到 B 的右節(jié)點 E，此時， E 節(jié)點 的剩余容量 r=4 ，v=9, 選擇 w3=2, 符合要求， 節(jié)點 E 成為當前的擴展節(jié)點，進入節(jié)點 J, 此時， 節(jié)點 J 的剩余容量 r=2 ， v=16 ，選擇 w4=1, 符合要求，到葉子節(jié)點 T，此時，節(jié)點 T 的剩余 容量 r=1 ， v=20 ；因此得到一個可行解，即

12、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, 得到一個可行解 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)解。五、算法測試代碼：#include #include in

13、t n;/ 物品數(shù)量double c;/ 背包容量double v100;/各個物品的價值double w100;/各個物品的重量double cw = 0.0;/當前背包重量double cp = 0.0;/當前背包中物品價值double bestp = 0.0;/當前最優(yōu)價值double perp100;/單位物品價值排序后int order100;/物品編號int put100;/ 設置是否裝入/ 按單位價值排序 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);/ 計算上界函數(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;printf（ 請輸入物品的重量和價值： ）;for（i=