解01背包問題的動態(tài)規(guī)劃算法(共6頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上解0/1背包問題的動態(tài)規(guī)劃算法摘要：本文通過研究動態(tài)規(guī)劃原理，提出了根據(jù)該原理解決背包問題的方法與算法實現(xiàn)，并對算法的正確性作了驗證觀察程序運行結(jié)果，發(fā)現(xiàn)基于動態(tài)規(guī)劃的算法能夠得到正確的決策方案且比窮舉法有效關鍵字：動態(tài)規(guī)劃；背包；約束條件；序偶；決策序列；支配規(guī)則1、引 言 科學研究與工程實踐中，常常會遇到許多優(yōu)化問題，而有這么一類問題，它們的活動過程可以分為若干個階段，但整個過程受到某一條件的限制。這若干個階段的不同決策的組合就構(gòu)成一個完整的決策。0/1背包問題就是一個典型的在資源有限的條件下，追求總的收益最大的資源有效分配的優(yōu)化問題。對于0/1背包問題，我們可以

2、這樣描述：設有一確定容量為C的包及兩個向量C=（S1，S2，Sn）和P=（P1，P2，PN），再設X為一整數(shù)集合，即X=1，2，3，N，X為SI、PI的下標集，T為X的子集，那么問題就是找出滿足約束條件Si=C，使PI獲得最大的子集T。在實際運用中，S的元素可以是N個經(jīng)營項目各自所消耗的資源，C可以是所能提供的資源總量，P的元素可是人們從各項項目中得到的利潤。0/1背包問題是工程問題的典型概括，怎么樣高效求出最優(yōu)決策，是人們關心的問題。2、求解問題的動態(tài)規(guī)劃原理與算法21動態(tài)規(guī)劃原理的描述求解問題的動態(tài)規(guī)劃有向前處理法向后處理法兩種，這里使用向前處理法求解0/1背包問題。對于0/1背包問題，可

3、以通過作出變量X1，X2，XN的一個決策序列來得到它的解。而對于變量X的決策就是決定它是取0值還是取1值。假定決策這些X的次序為Xn，XN-1，X0。在對X0做出決策之后，問題處于下列兩種狀態(tài)之一：包的剩余容量是M，沒任何效益；剩余容量是M-w，效益值增長了P。顯然，之后對Xn-1，Xn-2，X1的決策相對于決策X所產(chǎn)生的問題狀態(tài)應該是最優(yōu)的，否則Xn，X1就不可能是最優(yōu)決策序列。如果設Fj（X）是KNAP（1，j，X）最優(yōu)解的值，那么Fn（M）就可表示為 FN（M）=max(fn(M),fn-1(M-wn)+pn) （1） 對于任意的fi(X),這里i>0，則有 fi(X)=maxfi

4、-1(X),fi-1(X-wi)+pi （2） 為了能由前向后推而最后求解出FN（M），需從F0（X）開始。對于所有的X>=0,有F0（X）=0，當X<0時，有F0（X）等于負無窮。根據(jù)（2），可求出0XW1和X=W1情況下F1（X）的值。接著由（2）不斷求出F2，F(xiàn)3，F(xiàn)N在X相應取值范圍內(nèi)的值。22 0/1背包問題算法的抽象描述(1) 初始化各個元素的重量Wi、效益值Pi、包的最大容量M；(2) 初始化0；(3) 生成Si；a 在中i-1找滿足約束條件的第R對序偶；b 生成S1i ;c 清除不滿足條件的序偶；d 將Sn-1中滿足條件的序偶復制到Sn 中；（4）對Sn+1置初值；

5、（5）若不滿足循環(huán)次數(shù)轉(zhuǎn)（3）,否則轉(zhuǎn)（）；（6）用回溯法確定決策序列；終止程序。23計算復雜性分析假設Si的序偶是|i |。在i的情況下，每個i由1i-1和1i歸并而成，并且1i |<=|i-1 |,因此i |<=2|i-1 |。在最壞情況下沒有序偶被清除，所以對|i|求和(i=0,1,2,n-1)的結(jié)果是n-1,也就是說的空間復雜度為（n）。由i-1生成i需要|i-1|的時間，所以在計算S0，S1，S2，Sn-1時所消耗的總時間為（|i-1|），0in。由于in，所以計算這些i總的時間為（n）。該算法的時間復雜性為（n），似乎表明當很大時它的有效性不會讓人滿意，但由于支配規(guī)則的

6、引入，很好的清除了不滿足約束的序偶，因而該算法在很多情況下都能在可接受的時間內(nèi)求出決策序列?；趧討B(tài)規(guī)劃的算法源程序由于算法源程序有一定的篇幅，將其附后。3、性能測試 測試問題為了驗證算法的正確性與有效性，用兩個數(shù)組和分別存儲始記錄和P，記錄為用窮舉法已求出最優(yōu)決策的實例?，F(xiàn)分別取3，4 ，6，10進行實驗。32試驗結(jié)果與分析 為了便于說明問題，現(xiàn)將實驗過程中的N取不同值的一組向量和P（也就是重量與效益值）記錄如下：N=3：=（2，3，4）；P=（1，2，5）；M=6；N=4：=（2，4，6，7）；P=（6，10，12，13）；M=11；N=6：=（100，50，20，10，7，3）；P=（9

7、0，70，30，20，5，15）；M=165；N=10：=（2，4，5，7，10，14，19，20，25，30）； P=（1，3，4，5，10，15，20，25，36，28）；M=70；運行程序，與上述實例對應的決策序列為（1 0 1）、（0 1 0 1）、（1 1 0 1 1）和（0 0 1 1 0 1 1 0 1 0），各決策序列與窮舉法得到的結(jié)果一致，得到了最大的效益值，都為有限資源下的最優(yōu)決策序列。根據(jù)程序運行的中間結(jié)果，記錄上述實例每次的Si的序偶個數(shù)，結(jié)果如下表：Si的序偶個數(shù)表：Si的個 數(shù) NS0S1S2S3S4S5S6S7S8S931244124561246112110124

8、781215222732觀察分析Si序偶的個數(shù)可以發(fā)現(xiàn)，運用動態(tài)規(guī)劃思想的算法，隨著N的增大，對于每一個Si并非都是|Si|= =2|Si-1|,尤其當i>4時效果更加明顯，減少了搜索的范圍，避免了窮舉搜索，比窮舉法有效，結(jié)束語通過將動態(tài)規(guī)劃原理引入到解背包問題中，由于支配規(guī)則的高效性，使該算法比運用窮舉思想的算法有效需要指出的是，由于它的時間復雜性為（n），背包問題是一個難問題。如果能夠?qū)⑺禐槎囗検綇碗s性，那么所有的難問題就都可以在多項式時間內(nèi)求解，這將會大大提高現(xiàn)行些類問題的算法的可靠性與效率。在這方面，有待深入研究，也是值得研究的問題。參考文獻：1 數(shù)據(jù)結(jié)構(gòu)：C語言版/嚴蔚敏等編

9、著。2 語言程序設計：潭浩強編著。3 計算機算法基礎:第二版/余祥宣等編著。用動態(tài)規(guī)劃解0/1背包問題的源程序代碼：#include<stdio.h>#include<math.h>#define n 6void DKNAP();main() int pn+1,wn+1; int M,m=1,i,j; for(i=1;i<=n;i+) m=m*2; printf("nin put the weight and the p:"); scanf("%d %d",&wi,&pi); printf("%d&

10、quot;,m); printf("n in put the max weight M:"); scanf("%d",&M); DKNAP(p,w,M,m);void DKNAP(int p,int w,int M,int m) int p2m,w2m,pp,ww,px; int Fn+1,pk,q,k,l,h,u,i,j,next,max,sn+1; F0=1; p21=w21=0; l=h=1; F1=next=2; for(i=1;i<n;i+) k=l; max=0； u=l; for(q=l;q<=h;q+) if(w2q+

11、wi<=M)&&max<=w2q+wi) u=q; max=w2q+wi; for(j=l;j<=u;j+) pp=p2j+pi; ww=w2j+wi; while(k<=h&&w2k<ww) p2next=p2k; w2next=w2k; next+; k+; if(k<=h&&w2k=ww) if(pp<=p2k) pp=p2k; k+; else if(pp>p2next-1) p2next=pp; w2next=ww;next+; while(k<=h&&p2k<=p2next-1)k+; while(k<=h) p2next=p2k; w2next=w2k; next=next+1; k+; l=h+1; h=next-1; Fi+1=next; for(i=1;i<next;i+) printf("%2d%2d ",p2i,w2i); for(i=n;i>0;i-) next=Fi; next-; pp=pk=p2next; ww=w2next; while(ww+wi>M&&next>Fi-1) next=next-1; pp=p2next; ww=w2next; i