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

《動(dòng)態(tài)規(guī)劃與回溯法解決0-1背包問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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＝7i1234w(重量)3521v(價(jià)值)91074原理：　　動(dòng)態(tài)規(guī)劃與分治法類似，都是把大問題拆分成小問題，通

2、過尋找大問題與小問題的遞推關(guān)系，解決一個(gè)個(gè)小問題，最終達(dá)到解決原問題的效果。但不同的是，分治法在子問題和子子問題等上被重復(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è)

3、物品的體積（重量）；　　b)?建立模型，即求max(V1X1+V2X2+…+VnXn)；　　c)?約束條件，W1X1+W2X2+…+WnXn

4、n)是01背包問題的最優(yōu)解，則有(X2，X3，…，Xn)是其子問題的最優(yōu)解，　　　　假設(shè)(Y2，Y3，…，Yn)是上述問題的子問題最優(yōu)解，則理應(yīng)有(V2Y2+V3Y3+…+VnYn)+V1X1?>(V2X2+V3X3+…+VnXn)+V1X1；..　　　　而(V2X2+V3X3+…+VnXn)+V1X1=(V1X1+V2X2+…+VnXn)，則有(V2Y2+V3Y3+…+VnYn)+V1X1?>?(V1X1+V2X2+…+VnXn)；　　　　該式子說明(X1，Y2，Y3，…，Yn)才是該01背包問題的最優(yōu)

5、解，這與最開始的假設(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)的一個(gè)，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝　　　　　　　其中V(i-1,j)表示不裝，V(

6、i-1,j-w(i))+v(i)?表示裝了第i個(gè)商品，背包容量減少w(i)但價(jià)值增加了v(i)；　　　　由此可以得出遞推關(guān)系式：　　　　1)?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à)值)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即m[1][c

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

8、.序號(hào)WeightValue123456713947111316202025104711111114173274711111111114144444444從表格中可以看出背包的最大價(jià)值value=20，即當(dāng)X1=1，X2=0，X3=1，X4=1。五、算法測(cè)試代碼：#include#include#include#include#include