動(dòng)態(tài)規(guī)劃法求解背包問(wèn)題

算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告

第三次實(shí)驗(yàn)姓名學(xué)號(hào)班級(jí)時(shí)間11.14上午地點(diǎn)工訓(xùn)樓309實(shí)驗(yàn)名稱動(dòng)態(tài)規(guī)劃法求解背包問(wèn)題實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)上機(jī)實(shí)驗(yàn)，要求掌握動(dòng)態(tài)規(guī)劃算法的問(wèn)題描述、算法設(shè)計(jì)思想、程序設(shè)計(jì)。實(shí)驗(yàn)原理給定任意幾組數(shù)據(jù)，利用動(dòng)態(tài)規(guī)劃法的思想，把0-1背包裝滿并使得其價(jià)值最大。程序思路：（1） 首先從剩余容量是考慮當(dāng)前物品能不能放入背包；（2） 其次從價(jià)值上考慮當(dāng)前物品要不要放入背包，是不是最優(yōu)的。實(shí)驗(yàn)步驟找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征（利用反證法）。遞歸的定義最優(yōu)值。噸,■/）=（ 『?1 2■” （3-4-3）fv J>w朋（唧）彳：J：” （3.4.4）以自底向上的方法計(jì)算最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)的信息構(gòu)造最優(yōu)解。關(guān)鍵代碼voidKnapsack(intv[],intw[],intc,intn,int**m){〃初始化0-1背包表格intjmax=min(w[n],c);〃背包剩余容量上限，范圍[0?w[n])(左閉右開(kāi)區(qū)間)for(intj=0;jvjmax;j++)m[n][j]=0;for(intj=w[n];j<=c;j++) 〃限制范圍[w[n]~c]m[n][j]=v[n];

〃利用最優(yōu)子結(jié)構(gòu)性質(zhì)，從最后一個(gè)元素開(kāi)始，利用遞推公式for(inti=n-l;i>=l;i--){jmax=min(w[n],c); 〃第一種情況，背包剩余容量j在區(qū)間[O,jmax),該物品不能放入背包for(intj=O;jvjmax;j++)m[i][j]=m[i+1][j]; 〃沒(méi)產(chǎn)生任何效益for(intj=w[i];j<=c;j++) 〃第二種情況，背包剩余容量j在區(qū)間[w[i],c]m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); 〃根據(jù)效益值增加vi，選擇該物品放入背包或者不放入背包}}不同之處在于0<L表格的第一行的填法〃x[]數(shù)組存儲(chǔ)對(duì)應(yīng)物品不同之處在于0<L表格的第一行的填法voidTraceback(int**m,intw[],intc,intn,intx[]){for(inti=1;i<n;i++){if(m[i][c]==m[i+1][c])〃若前一個(gè)和后一個(gè)效益值比沒(méi)變化，說(shuō)明該物品沒(méi)放入背包中x[i]=0;else 〃否則放入了背包中，由m[2][c-w1]繼續(xù)構(gòu)造最優(yōu)解{x[i]=1;c-=w[i];}}x[n]=(m[n][c])?1:0; 〃最后一個(gè)元素需要單獨(dú)判斷for(inti=n-1;i>1;i--){//背包不同剩余容量//背包不同剩余容量jv=jmaxvc〃沒(méi)產(chǎn)生任何效益for(intj=0;j<=jmax;j++)m[i][j]=m[i+1][j];for(intj=w[i];jv=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]單獨(dú)拿出來(lái)計(jì)算，是為了計(jì)算的方便，并不需要在和前面一樣的麻煩，只有判斷最后一步就可以m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);

輸入及背包容量較小的結(jié)果（數(shù)據(jù)手動(dòng)收入）:'F:\算法實(shí)驗(yàn)憧驗(yàn)^動(dòng)態(tài)規(guī)劃法乜已ro-□nel\Debug\^ero-onel.exe(Ctrl4-Shift4-特裝物品的價(jià)值為:1243Thetimeis0.021特裝物品的價(jià)值為:1243Thetimeis0.021J2)F:\算法實(shí)驗(yàn)\實(shí)驗(yàn)二動(dòng)態(tài)規(guī)劃法\zeroonel\Debug\zero-onel.exe測(cè)試結(jié)果入物&物6—龔71裝71測(cè)試結(jié)果入物&物6—龔71裝71包包請(qǐng)待24待24背背16斗..■■■?■56值為:1價(jià)號(hào)_b^59為59的編脊個(gè)值50量50大品出的價(jià)1重1曰粉□.1.1□nr^u-6-IZ7-T6-TT-T-TT-T0

T_Ln.B3.B3.B.B118244182441945419454207322073217778263501777826350Thetimeis0.062輸入及背包容量較大的結(jié)果（數(shù)據(jù)由隨機(jī)函數(shù)產(chǎn)生）:亙3F:\算法實(shí)驗(yàn)\實(shí)驗(yàn)二詼態(tài)規(guī)劃法乜呂『09門(mén)elXDebug\zero-onel.exe100&0&0100278062785121408713529818193441228148662508?484217986128356451301164448146422613829180223882274601827029278062785121408713529818193441228148662508?484217986128356451301164448146422613829180223882274601827029228792311391411399606868502508425104193912031518237187962856030845100701916726933265731687618895265171776516445967831235642810582117821793830984262452556220394322276662068218833095323082295914850185381078022161098947015304127172928554922235516514104271336030496105822478621108281562458814863247981576994412554816690126061104116912594642843635292252449132676待裝物品的重量為:1211631594143262780627051214087135298181934412281486625087484217986228792311391411283564513011644481464226138291802238822746018270291399606868502508425104193912031518237187962856030845100701916726933265731687618895265171776516445967831235642810582117821793830984262452556220394322276662068218833095323082295914850185381078022161098947015304127172928554922235516514104271336030496105822478621108281562458814863247981576994412554816690126061104116912594642843635292252449132676背包能裝的最大的價(jià)值為:1000000背包裝下的物品編號(hào)為：4243454G47485052S354555G575860G162636465666768G970717273747677787980818283848586878889909192949596979899100Thetimeis6.081

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

intmain(){intc,n;coutvv"請(qǐng)輸入背包的容量:cin>>c;coutvv"請(qǐng)輸入物品的個(gè)數(shù):cin>>n;//下標(biāo)從1開(kāi)始int//下標(biāo)從1開(kāi)始int*w=newint[n+1];intx[N+1];int**m;inti;m=newint*[n+1];for(i=0;ivn+1;i++){m[i]=newint[c];手動(dòng)輸入的代碼部分******/*coutvv"待裝物品的重量為："vvendl;for(i=1;iv=n;i++)cin>>w[i];coutvvendl;coutvv"待裝物品的價(jià)值為："vvendl;for(i=1;iv=n;i++)cin>>v[i];coutvvendl;*/隨機(jī)生成數(shù)據(jù)部分******ran(v,n);coutvv"待裝物品的價(jià)值為："vvendl;for(i=1;iv=n;i++)coutvvv[i]vv"";coutvvendl;ran(w,n);coutvv"待裝物品的重量為："vvendl;for(i=1;iv=n;i++)coutvvw[i]vv"";coutvvendl;clock_tstart,end,over; //計(jì)算程序運(yùn)行時(shí)間的算法start=clock();end=clock();over=end-start;start=clock();

Knapsack(v,w,c,n,m); //函數(shù)調(diào)用，求解0-1背包問(wèn)題coutvv"背包能裝的最大的價(jià)值為："vvm[l][c]vvendl;Traceback(m,w,c,n,x); //函數(shù)調(diào)用，構(gòu)造最優(yōu)解coutvv"背包裝下的物品編號(hào)為："vvendl;for(i=l;iv=n;i++){if(x[i]==l)coutvvivv"";}coutvvendl;coutvvendl;end=clock();printf("Thetimeis%6.3f",(double)(end-start-over)/CLK_TCK);//顯示運(yùn)行時(shí)間for(i=0;ivn+l;i++) //刪除動(dòng)態(tài)分配的內(nèi)存{delete[]m[i];}delete[]m;delete[]v;delete[]w;system("pause");return0;}******課本上的源代碼部分******/*voidKnapsack(intv[],intw[],intc,intn,intm[][l0]){intjmax=min(w[n]-1,c); 〃背包剩余容量上限，范圍0?w[n]-1for(intj=0;jv=jmax;j++)〃限制范圍[w[n]?〃限制范圍[w[n]?c]〃背包不同剩余容量jv=jmaxvc//沒(méi)產(chǎn)生任何效益for(intj=w[n];jv=c;j++)m[n][j]=v[n];for(inti=n-1;i>1;i--){jmax=min(w[n]-1,c);for(intj=0;jv=jmax;j++)m[i][j]=m[i+1][j];for(intj=w[i];jv=c;j++)//for(intj=w[i];jv=c;j++)//背包不同剩余容量j-w[i]>c}m[l][c]=m[2][c];if(c>=w[l])m[l][c]=max(m[l][c],m[2][c-w[l]]+v[l]);}*/voidKnapsack(intv[],intw[],intc,int