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

算法分析與設計實驗報告

第三次實驗姓名學號班級時間上午地點工訓樓實驗名稱動態(tài)規(guī)劃法求解背包問題實驗目的通過上機實驗，要求掌握動態(tài)規(guī)劃算法的問題描述、算法設計思想、程序設計。實驗原理給定任意幾組數(shù)據(jù)，利用動態(tài)規(guī)劃法的思想，把0-1背包裝滿并使得其價值最大。程序思路：（1）首先從剩余容量是考慮當前物品能不能放入背包；（2）其次從價值上考慮當前物品要不要放入背包，是不是最優(yōu)的。實驗步驟①找出最優(yōu)解的性質(zhì)，并刻畫其結構特征（利用反證法）。②遞歸的定義最優(yōu)值。岫力=「1門―（必〕現(xiàn)+L力OMj<明（V/>W飽%j）=：n微您③以自底向上的方法計算最優(yōu)值。④根據(jù)計算最優(yōu)值時的信息構造最優(yōu)解。關鍵代碼voidKnapsack(intv[],intw口,intc,intn,int**m){〃初始化0-1背包表格intjmax=min(w[n],c);〃背包剩余容量上限，范圍[0~亞[口])(左閉右開區(qū)間)for(intj=0;j<jmax;j++)m[n][j]=0；for(intj=w[n];j<=c;j++)//限制范圍[w[n]~c]m[n][j]=v[n]；

〃利用最優(yōu)子結構性質(zhì)，從最后一個元素開始，利用遞推公式for(inti=n-1;i>=1;i--){jmax=min(w[n],c);〃第一種情況，背包剩余容量j在區(qū)間[0,jmax)，該物品不能放入背包for(intj=0;j<jmax;j++)m[i][j]=m[i+1][j];〃沒產(chǎn)生任何效益for(intj=w[i];j<=c;j++)〃第二種情況，背包剩余容量上在區(qū)間[w[i],c]m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);〃根據(jù)效益值增加vi，選擇該物品放入背包或者不放入背包}不同之在0-1//x口數(shù)組存儲對應物品不同之在0-1voidTraceback(int**m,intw[],intc,intn,intx[]){for(inti=1;i<n;i++){if(m[i][c]==m[i+1][c])〃若前一個和后一個效益值比沒變化，說明該物品沒放入背包中x[i]=0;else〃否則放入了背包中，由m[2][c-w1]繼續(xù)構造最優(yōu)解{x[i]=1;c-=w[i];}}x[n]=(m[n][c])?1:0;〃最后一個元素需要單獨判斷}for(inti=n-1;i>1;i--){jmax=min(w[n]-1,c);for(intj=0;j<=jmax;j++)〃背包不同剩余容量j<=jmax<cm[i][j]=m[i+1][j];〃沒產(chǎn)生任何效益for(intj=w[i];j<=c;j++)〃背包不同剩余容量j-w[i]>cm[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);/效益值增加vi}〃之所以講m[1][c]單獨拿出來計算，是為了計算的方便，并不需要在和前面一樣的麻煩，只有判斷最后一步就可以m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);輸入及背包容量較小的結果（數(shù)據(jù)手動收入）：測試結果B1S&SSkS^^Vs'FO-onelXDebucXzero-cjrelexe輸入及背包容量等大小的結果（數(shù)據(jù)由隨機函數(shù)產(chǎn)生）:待裝物品的價值為裝的大的價值為品編號為:6LMIV6L^iV3.rtn3—ou.&u46口nn46裝下測試結果B1S&SSkS^^Vs'FO-onelXDebucXzero-cjrelexe輸入及背包容量等大小的結果（數(shù)據(jù)由隨機函數(shù)產(chǎn)生）:待裝物品的價值為裝的大的價值為品編號為:6LMIV6L^iV3.rtn3—ou.&u46口nn46裝下八人物&坳6量型瞿71裝71包包E主QE寺?4寺?4匕弓匕弓1日嶄為5?的編答人值50量50一人品16耳/:56值為:1價號182441824475tineis0.3621945420732194542073217778177782635B26350輸入及背包容量較大的結果（數(shù)據(jù)由隨機函數(shù)產(chǎn)生）:S3F謨法實郢噬二檄］宏郎「7口「el\Debig\zerc-orel.=*xe100121U315941432G22879231139141278B6270512140H?13E2981S19344123314SS62E0874542179恥121U315941432G22879231139141139?606BE85B25884251眄19391203151823?18796疑5603酬4510070191672G933265731G87S18895265171776516445967331235S428105321178317938309S426245255622839432227G66206821383309E323B92295914B501853B107803216109B947015304127172?2055492223551651410427133603049610582247862110828156245M1486324798157S99441255481ES901360S1104116912594E42843635293252449132676摩物品的重量為：121U315941432G278B6270512140H?13E2981S19344123314SS62E0874542179恥22879231139141128356451301164448146422(13B291B0223S82274601827029139?606BE85B25884251眄19391203151823?18796疑5603酬4510070191672G933265731G87S18895265171776516445967331235S428105321178317938309S426245255622839432227G66206821383309E323B92295914B501853B107803216109B947015304127172?2055492223551651410427133603049610582247862110828156245M1486324798157S99441255481ES901360S1104116912594E42843635293252449132676勺：10000B0己Jj■司-1士■.fT-'J-^r-.ii―?,=__nH已不：UT；J口二卅I\i....'J：慳434546474日E05253545E5557E8EB6162636465E66768697071727374?G77?87980818283S485B68?8G的9091929495魅979099100Ihetimeis6.0B1

實驗心得對于這一次的實驗，利用動態(tài)規(guī)劃的算法求解背包問題，雖然課本上有函數(shù)的實現(xiàn)但是實驗做起來還是有一定的難度的，畢竟我們追求的不是將代碼敲出來而是真正掌握了這一個經(jīng)典的算法實例。首先我是自己寫了主函數(shù)，然后照著課本敲的代碼，然后自己一步步分析代碼中的不足的部分，加以完善，后來經(jīng)過自己對于這個問題的理解，發(fā)現(xiàn)課本上的代碼有一些不太容易理解的地方，就按照自己的理解進行了一些改變，最終實現(xiàn)了將自己的理解與代碼完全融合，后來自己又仔細研究了一下書上的代碼，發(fā)覺自己的代碼效率不高，就有進行了改進，最終得到了較為滿意的代碼。不過在實驗過程中也遇到了很多的問題，最主要的問題是經(jīng)常出現(xiàn)中斷，這使我很郁悶，不過好在在同學的幫助下都順利解決了，感覺很開心，然后由于要測試大數(shù)據(jù)，所以采用了隨機生成函數(shù)，以及動態(tài)分配內(nèi)存，學的利用到很多以前不太用到的知識，感覺棒棒的。實驗比較觀察上面三種不同數(shù)據(jù)規(guī)模的輸入，我們可以看到當物品的數(shù)量比較多的時候，算法是比較浪費時間的，其次是背包的容量也是一種限制性因素，而且采用隨機生成函數(shù)有一點不好的就是生成的數(shù)據(jù)都是比較大的，有點不符合實際，我想在實際問題處理中應該采用的是讀文件的方式輸入的吧，不然采用手動輸入，還是十分麻煩的。實驗得分助教簽名附錄：完整代碼//0-1背包問題，動態(tài)規(guī)劃算法#include<iostream>#include<time.h>#include<iomanip>usingnamespacestd;constintN=100;voidKnapsack(intv[],intw[],intc,intn,int**m);voidTraceback(int**m,intw[],intc,intn,intx[]);voidran(int*input,intn)//隨機生成數(shù)組元素函數(shù){inti;srand(time(0));for(i=1;i<=n;i++)input[i]=rand();//input[i]='\0';

intmain()(intc,n;cout<<”請輸入背包的容量：”；cin>>c;cout<<”請輸入物品的個數(shù)：”；cin>>n;int*v=newint[n+1];int*w=newint[n+1];//下標從1開始intx[N+1];int**m;inti;m=newint*[n+1];for(i=0;i<n+1;i++)(m[i]=newint[c];}******手動輸入的代碼部分******/*cout<<"待裝物品的重量為："<<endl;for(i=1;i<=n;i++)cin>>w[i];cout<<endl;cout<<"待裝物品的價值為："<<endl;for(i=1;i<=n;i++)cin>>v[i];cout<<endl;*/小小小小小小隨機生成數(shù)據(jù)部分小小小小小小隨機生成數(shù)據(jù)部分******ran(v,n);cout<<"待裝物品的價值為："<<endl;for(i=1;i<=n;i++)cout<<v[i]<<"";cout<<endl;ran(w,n);cout<<"待裝物品的重量為："<<endl;for(i=1;i<=n;i++)cout<<w[i]<<"";cout<<endl;clock_tstart,end,over;//計算程序運行時間的算法start二clock();end二clock();over二end-start;start二clock();

Knapsack(v,w,c,n,m);//函數(shù)調(diào)用，求解0-1背包問題cout<<"背包能裝的最大的價值為："<<m[1][c]<<endl;Traceback(m,w,c,n,x);//函數(shù)調(diào)用，構造最優(yōu)解cout<<"背包裝下的物品編號為："<<endl;for(i=1;i<=n;i++){if(x[i]==1)cout<<i<<"";}cout<<endl;cout<<endl;end=clock();printf("Thetimeis%6.3f",(double)(end-start-over)/CLK_TCK);//顯示運行時間for(i=0;i<n+1;i++)//刪除動態(tài)分配的內(nèi)存{delete[]m[i];}delete[]m;delete[]v;delete[]w;system("pause");return0;}******課本上的源代碼部分******/*voidKnapsack(intv[],intw[],intc,intn,intm[][10]){intjmax=min(w[n]-1,c);〃背包剩余容量上限，范圍0~w[n]-1for(intj=0;j<=jmax;j++)m[n][j]=0;for(intj=w[n];j<=c;j++)〃限制范圍[w[n]~c]m[n][j]=v[n];for(inti=n-1;i>1;i--){〃背包不同剩余容量j<=jmax<c〃背包不同剩余容量j<=jmax<c//沒產(chǎn)生任何效益for(intj=0;j<=jmax;j++)m[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)〃背包不同剩余容量^國工for(intj=w[i];j<=c;j++)〃背包不同剩余容量^國工m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);〃效益值增加vi}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}*/voidKnapsack(intv[],intw[],intc,intn,int**m){//初始化0-1背包表格intjmax=min(w[n],c);〃背包剩余容量上限，范圍[0~卬[口])(左閉右開區(qū)間)for(intj=0;j<jmax;j++)m[n][j]=0;for(intj=w[n];j<=c;j++)〃限制范圍[w[n]~c]m[n][j]=v[n];//利用最優(yōu)子結構性質(zhì)，從最后一個元素開始，利用遞推公式for(inti=n-1;i>=1;i--){jmax=min(w[n],c);〃第一種情況，背包剩余容量上在區(qū)間[0,jmax)，該物品不能放入背包for(intj=0;j<jmax;j++)m[i][j]=m[i+1][j];//沒產(chǎn)生任何效益for(intj=