動態(tài)規(guī)劃法求解背包問題

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第三次實(shí)驗(yàn)姓名學(xué)號班級時間11.14上午地點(diǎn)工訓(xùn)樓309實(shí)驗(yàn)名稱動態(tài)規(guī)劃法求解背包問題實(shí)驗(yàn)?zāi)康耐ㄟ^上機(jī)實(shí)驗(yàn)，要求掌握動態(tài)規(guī)劃算法的問題描述、算法設(shè)計(jì)思想、程序設(shè)計(jì)。實(shí)驗(yàn)原理給定任意幾組數(shù)據(jù)，利用動態(tài)規(guī)劃法的思想，把0-1背包裝滿并使得其價值最大。程序思路：（1）首先從剩余容量是考慮當(dāng)前物品能不能放入背包；（2）其次從價值上考慮當(dāng)前物品要不要放入背包，是不是最優(yōu)的。實(shí)驗(yàn)步驟 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征（利用反證法）。 遞歸的定義最優(yōu)值。 以自底向上的方法計(jì)算最優(yōu)值。 根據(jù)計(jì)算最優(yōu)值時的信息構(gòu)造最優(yōu)解。void Knapsack( int v, int w, int

2、c, int n, int m)/初始化0-1背包表格int jmax=min(wn,c);/背包剩余容量上限，范圍0wn)(左閉右開區(qū)間)for (int j=0;jvjmax;j+)m nj=0;for (int j=wn;j<=c;j+)/ 限制范圍wncm nj=v n;/利用最優(yōu)子結(jié)構(gòu)性質(zhì)，從最后一個元素開始，利用遞推公式for (int i=n-1;i>=1;i-)jmax=min(wn,c);/第一種情況，背包剩余容量j在區(qū)間0,jmax)，該物品不能放入背包for (int j=0;j<jmax;j+)mij=mi+1j;/沒產(chǎn)生任何效益for (int j=

3、wi;j<=c;j+)/ 第二種情況，背包剩余容量j在區(qū)間wi,cmij=max(mi+1j,mi+1j-wi+vi);/關(guān)鍵代碼不同之處在于o0表格的第一行的填法根據(jù)效益值增加vi，選擇該物品放入背包或者不放入背包/x數(shù)組存儲對應(yīng)物品0-1向量，不裝入背包，裝入背包void Traceback( int *m, int w, int c, int n, int x)for (int i=1;i<n;i+)if (mic=mi+1c)/若前一個和后一個效益值比沒變化，說明該物品沒放入背包中xi=0;else /否則放入了背包中，由m2c-w1繼續(xù)構(gòu)造最優(yōu) 解xi=1; c-=wi;

4、xn=(mnc)?1:0;/最后一個元素需要單獨(dú)判斷for(int i=n-1;i>1;i-)jmax=mi n(wn-1,c);for(int j=O;jv=jmax;j+)/ 背包不同剩余容量jv=jmax<cmij=mi+1j;/沒產(chǎn)生任何效益for(int j=wi;j<=c;j+)/ 背包不同剩余容量j-wi>cmij=max(mi+1j,mi+1j-wi+vi);/ 效益值增加vi/之所以講m1c單獨(dú)拿出來計(jì)算，是為了計(jì)算的方便，并不需 要在和前面一樣的麻煩，只有判斷最后一步就可以m1c=m2c;if(c>=w1)m1c=max(m1c,m2c-w1+

5、v1);測試結(jié)果輸入及背包容量較小的結(jié)果（數(shù)據(jù)手動收入）-F;算潼主堂0峻二就危規(guī)勁法Eb7 建項(xiàng)自（匚 tri-I-Shift + Mi |恃裝掬品的價值兩L 2 4 3o-n e 1D e-buqxe:ro- 口【門 u 1» exu輸入及背包容量中等大小的結(jié)果（數(shù)據(jù)由隨機(jī)函數(shù)產(chǎn)生）SJ®"J47ero-onelDebugTero-on el. exe101 1 jp 0 & & y/ I 10M 辦54值均 ;1 '價號 =羲為59為59的編 容個值雪聶大盤 Es-i*!rF_JJOJ & -A- 6 0 t 匚 口-m 3

6、fiM 3 JDJ5 1 非覇品覽品46萊下y 人入物6物&曙$ 71裝71包包 718244time is H.HbZ輸入及背包容量較大的結(jié)果（數(shù)據(jù)由隨機(jī)函數(shù)產(chǎn)生）口-orclS Debugero-c iftel.cxei 陽*JL0O2V8Hb al 214HH V13L> 29HLH IV344 122H 14Kb& 2hAY 4M42 17VBb1005 6-®l 301U 444« 1464?291SP 2nR；» 曲乂27A27或忙,：世 t址 fLdJW雖L_：*i<Lc或？BET：Pij£盂 ivfekUFFm

7、TFTnI 解重.常工 Iff I' 卡 F 亍 I""f 卡 1： I? I.電才匚#JE *聊工 Ji 二耳i 1 屮左 ? y. yi.、jip【（.vrjfr*s 黑 / 】託! :i 念 w*eij:.!:鼻 myi i 硏.吊The 1 lw lx 6 _fWl實(shí)驗(yàn)心得對于這一次的實(shí)驗(yàn)，利用動態(tài)規(guī)劃的算法求解 0-1背包問題，雖然課本上 有函數(shù)的實(shí)現(xiàn)但是實(shí)驗(yàn)做起來還是有一定的難度的，畢竟我們追求的不是將代碼敲出來而是真正掌握了這一個經(jīng)典的算法實(shí)例。首先我是自己寫了主函數(shù)， 然后照著課本敲的代碼，然后自己一步步分析代碼中的不足的部分，加以完善，后來經(jīng)過自己

8、對于這個問題的理解，發(fā)現(xiàn)課本上的代碼有一些不太容易理解的地方，就按照自己的理解進(jìn)行了一些改變，最終實(shí)現(xiàn)了將自己的理解與代碼完全融合，后來自己又仔細(xì)研究了一下書上的代碼，發(fā)覺自己的代碼效率不高， 就有進(jìn)行了改進(jìn)，最終得到了較為滿意的代碼。不過在實(shí)驗(yàn)過程中也遇到了很多的問題，最主要的問題是經(jīng)常出現(xiàn)中斷，這使我很郁悶，不過好在在冋學(xué)的幫助下都順利解決了， 感覺很開心，然后由于要測試大數(shù)據(jù)，所以采用了隨機(jī)生成函數(shù)，以及動態(tài)分配內(nèi)存，學(xué)的利用到很多以前不太用到的知識，感覺棒棒的。實(shí)驗(yàn)比較觀察上面三種不同數(shù)據(jù)規(guī)模的輸入，我們可以看到當(dāng)物品的數(shù)量比較多的時候，算法是比較浪費(fèi)時間的， 其次是背包的容量也是一種

9、限制性因素，而且采用隨機(jī)生成函數(shù)有一點(diǎn)不好的就是生成的數(shù)據(jù)都是比較大的，有點(diǎn)不符合實(shí)際，我想在實(shí)際問題處理中應(yīng)該采用的是讀文件的方式輸入的吧，不然采用手動輸入，還是十分麻煩的。實(shí)驗(yàn)得分助教簽名附錄：完整代碼0-1背包問題，動態(tài)規(guī)劃算法#include <iostream>#inelude <time.h>#include <iomanip> using namespacestd;const int N=100;void Knapsack( int v, int w, int c, int n, int *m); void Traceback( int *m,

10、 int w, int c, int n, int x);/隨機(jī)生成數(shù)組元素函數(shù)void ran( int *input,int n)int i;sran d(time(0);for (i=1;i<=n;i+)in puti=ra nd();/in puti='0'int main()int c,n;cout<< "請輸入背包的容量： " cin>>c;cout<< "請輸入物品的個數(shù)： " cin>>n;/ 下標(biāo)從 1開始int *v= new int n+1;int *w= new

11、 int n+1;int xN+1;int *m;int i;m=new int *n+1;for (i=0;i<n+1;i+) mi= new int c;* 手動輸入的代碼部分 */*cout<<" 待裝物品的重量為： "<<endl; for(i=1;i<=n;i+)cin>>wi; cout<<endl;cout<<" 待裝物品的價值為： for(i=1;i<=n;i+) cin>>vi;cout<<endl;*/* 隨機(jī)生成數(shù)據(jù)部分 * ran(v,n)

12、;cout<< "待裝物品的價值為： for (i=1;i<=n;i+) cout<<vi<< " " ;cout<<endl;ran(w,n);cout<< "待裝物品的重量為： for (i=1;i<=n;i+) cout<<wi<< " " ;cout<<endl;clock_t start,end,over; start=clock(); end=clock(); over=end-start; start=clock(

13、);"<<endl;" <<endl;" <<endl;/ 計(jì)算程序運(yùn)行時間的算法Knapsack(v,w,c,n,m);/函數(shù)調(diào)用，求解 0-1 背包問題cout<< "背包能裝的最大的價值為： " <<m1c<<endl;Traceback(m,w,c,n,x);/函數(shù)調(diào)用，構(gòu)造最優(yōu)解cout<< "背包裝下的物品編號為： " <<endl; for (i=1;i<=n;i+)if (xi=1)cout<<i

14、<< " " ;cout<<endl; cout<<endl; end=clock();printf( "The time is %6.3f" ,( double )(end-start-over)/CLK_TCK); / 顯 示運(yùn)行時間for (i=0;i<n+1;i+) / 刪除動態(tài)分配的內(nèi)存delete mi;delete m;delete v;delete w;system( "pause" ); return 0;* 課本上的源代碼部分 */*void Knapsack(int v,

15、int w,int c,int n,int m10) int jmax=min(wn-1,c); /背包剩余容量上限，范圍 0wn-1for(int j=0;j<=jmax;j+) mnj=0;for(int j=wn;j<=c;j+) / mnj=vn;限制范圍 wncfor(int i=n-1;i>1;i-) jmax=min(wn-1,c);for(int j=0;j<=jmax;j+)/mij=mi+1j;/背包不同剩余容量 j<=jmax<c 沒產(chǎn)生任何效益for(int j=wi;j<=c;j+) / 背包不同剩余容量 j-wi>c

16、mij=max(mi+1j,mi+1j-wi+vi); / 效益值增加 vi m1c=m2c;if(c>=w1)m1c=max(m1c,m2c-w1+v1);*/void Knapsack( int v, int / 初始化 0-1背包表格 int jmax=min(wn,c);開區(qū)間)for (int j=0;j<jmax;j+) mnj=0;for (int j=wn;j<=c;j+) mnj=vn;w, int c, int n, int *m)/ 背包剩余容量上限，范圍 0wn)( 左閉右/ 限制范圍 wncfor (int i=n-1;i>=1;i-) jmax=min(wn,c);0,jmax) ，該物品不能放入背包 for (int j=0;j<jmax;j+) mij=mi+1j;for (int j=wi;j<=c;j+)/ 利用最優(yōu)子結(jié)構(gòu)性質(zhì)，從最后一個元素開始，利用遞推公式/ 第一種情況，背包剩余容量 j 在