資源描述：
《解01背包問題的動態(tài)規(guī)劃算法.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、解0/1背包問題的動態(tài)規(guī)劃算法摘要：本文通過研究動態(tài)規(guī)劃原理，提出了根據(jù)該原理解決０／１背包問題的方法與算法實(shí)現(xiàn)，并對算法的正確性作了驗(yàn)證．觀察程序運(yùn)行結(jié)果，發(fā)現(xiàn)基于動態(tài)規(guī)劃的算法能夠得到正確的決策方案且比窮舉法有效．關(guān)鍵字：動態(tài)規(guī)劃；０／１背包；約束條件；序偶；決策序列；支配規(guī)則1、引言科學(xué)研究與工程實(shí)踐中，常常會遇到許多優(yōu)化問題，而有這么一類問題，它們的活動過程可以分為若干個階段，但整個過程受到某一條件的限制。這若干個階段的不同決策的組合就構(gòu)成一個完整的決策。0/1背包問題就是一個典型的在資源有限的條件下，追求總的收益最大的資源有效分配的優(yōu)化問題。對于0/1背包問題，
2、我們可以這樣描述：設(shè)有一確定容量為C的包及兩個向量C’=（S1，S2，……，Sn）和P=（P1，P2，……，PN），再設(shè)X為一整數(shù)集合，即X=1，2，3，……，N，X為SI、PI的下標(biāo)集，T為X的子集，那么問題就是找出滿足約束條件∑Si〈=C，使∑PI獲得最大的子集T。在實(shí)際運(yùn)用中，S的元素可以是N個經(jīng)營項(xiàng)目各自所消耗的資源，C可以是所能提供的資源總量，P的元素可是人們從各項(xiàng)項(xiàng)目中得到的利潤。0/1背包問題是工程問題的典型概括，怎么樣高效求出最優(yōu)決策，是人們關(guān)心的問題。2、求解問題的動態(tài)規(guī)劃原理與算法2．1動態(tài)規(guī)劃原理的描述求解問題的動態(tài)規(guī)劃有向前處理法向后處理法兩種，這
3、里使用向前處理法求解0/1背包問題。對于0/1背包問題，可以通過作出變量X1，X2，……，XN的一個決策序列來得到它的解。而對于變量X的決策就是決定它是取0值還是取1值。假定決策這些X的次序?yàn)閄n，XN-1，……，X0。在對X0做出決策之后，問題處于下列兩種狀態(tài)之一：包的剩余容量是M，沒任何效益；剩余容量是M-w，效益值增長了P。顯然，之后對Xn-1，Xn-2，……，X1的決策相對于決策X所產(chǎn)生的問題狀態(tài)應(yīng)該是最優(yōu)的，否則Xn，……，X1就不可能是最優(yōu)決策序列。如果設(shè)Fj（X）是KNAP（1，j，X）最優(yōu)解的值，那么Fn（M）就可表示為FN（M）=max(fn(M),fn
4、-1(M-wn)+pn)}?。?）對于任意的fi(X),這里i>0，則有fi(X)=max{fi-1(X),fi-1(X-wi)+pi}（2）為了能由前向后推而最后求解出FN（M），需從F0（X）開始。對于所有的X>=0,有F0（X）=0，當(dāng)X<0時，有F0（X）等于負(fù)無窮。根據(jù)（2），可求出0〈X〈W1和X〉=W1情況下F1（X）的值。接著由（2）不斷求出F2，F(xiàn)3，……，F(xiàn)N在X相應(yīng)取值范圍內(nèi)的值。2．20/1背包問題算法的抽象描述(1)初始化各個元素的重量W[i]、效益值P[i]、包的最大容量M；(2)初始化Ｓ0；6(1)生成Si；a．在中Ｓi-1找滿足約束條件的第
5、R對序偶；b．生成S1i;c．清除不滿足條件的序偶；d．將Sn-1中滿足條件的序偶復(fù)制到Sn中；（4）對Sn+1置初值；（5）若不滿足循環(huán)次數(shù)轉(zhuǎn)（3）,否則轉(zhuǎn)（６）；（6）用回溯法確定決策序列；終止程序。2．3計(jì)算復(fù)雜性分析假設(shè)Si的序偶是
6、Ｓi
7、。在i＞０的情況下，每個Ｓi由Ｓ1i-1和Ｓ1i歸并而成，并且｜Ｓ1i
8、<=
9、Ｓi-1
10、,因此｜Ｓi
11、<=2
12、Ｓi-1
13、。在最壞情況下沒有序偶被清除，所以對
14、Ｓi
15、求和(i=0,1,2,．．．n-1)的結(jié)果是２n-1,也就是說ＤＫＮＡＰ的空間復(fù)雜度為Ｏ（２n）。由Ｓi-1生成Ｓi需要
16、Ｓi-1
17、
18、的時間，所以在計(jì)算S0，S1，S
19、2，……，Sn-1時所消耗的總時間為（∑
20、Ｓi-1
21、），0〈＝i〈＝n－１。由于｜Ｓi｜〈＝２n，所以計(jì)算這些Ｓi總的時間為Ｏ（２n）。該算法的時間復(fù)雜性為Ｏ（２n），似乎表明當(dāng)Ｎ很大時它的有效性不會讓人滿意，但由于支配規(guī)則的引入，很好的清除了不滿足約束的序偶，因而該算法在很多情況下都能在可接受的時間內(nèi)求出決策序列。２．４基于動態(tài)規(guī)劃的算法源程序 由于算法源程序有一定的篇幅，將其附后。3、性能測試３．１測試問題為了驗(yàn)證算法的正確性與有效性，用兩個數(shù)組Ｐ［Ｎ］和Ｗ［Ｎ］分別存儲始記錄Ｃ’和P，記錄為用窮舉法已求出最優(yōu)決策的實(shí)例?，F(xiàn)分別取Ｎ＝3，4，6，10進(jìn)行實(shí)驗(yàn)。3．
22、2試驗(yàn)結(jié)果與分析為了便于說明問題，現(xiàn)將實(shí)驗(yà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=（90，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；運(yùn)行程序，與上述實(shí)例對應(yīng)的決策序列為（10
