动态规划法求解背包问题

算法分析与设计实验报告

第三次实验姓名学号班级时间11.14上午地点工训楼309实验名称动态规划法求解背包问题实验目的通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据，利用动态规划法的思想，把0-1背包装满并使得其价值最大。程序思路：（1） 首先从剩余容量是考虑当前物品能不能放入背包；（2） 其次从价值上考虑当前物品要不要放入背包，是不是最优的。实验步骤找出最优解的性质，并刻画其结构特征（利用反证法）。递归的定义最优值。吨,■/）=（ 『・1 2■” （3-4-3）fv J>w朋（唧）彳：J：” （3.4.4）以自底向上的方法计算最优值。根据计算最优值时的信息构造最优解。关键代码voidKnapsack(intv[],intw[],intc,intn,int**m){〃初始化0-1背包表格intjmax=min(w[n],c);〃背包剩余容量上限，范围[0〜w[n])(左闭右开区间)for(intj=0;jvjmax;j++)m[n][j]=0;for(intj=w[n];j<=c;j++) 〃限制范围[w[n]~c]m[n][j]=v[n];

〃利用最优子结构性质，从最后一个元素开始，利用递推公式for(inti=n-l;i>=l;i--){jmax=min(w[n],c); 〃第一种情况，背包剩余容量j在区间[O,jmax),该物品不能放入背包for(intj=O;jvjmax;j++)m[i][j]=m[i+1][j]; 〃没产生任何效益for(intj=w[i];j<=c;j++) 〃第二种情况，背包剩余容量j在区间[w[i],c]m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); 〃根据效益值增加vi，选择该物品放入背包或者不放入背包}}不同之处在于0<L表格的第一行的填法〃x[]数组存储对应物品不同之处在于0<L表格的第一行的填法voidTraceback(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[i]=1;c-=w[i];}}x[n]=(m[n][c])?1:0; 〃最后一个元素需要单独判断for(inti=n-1;i>1;i--){//背包不同剩余容量//背包不同剩余容量jv=jmaxvc〃没产生任何效益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]单独拿出来计算，是为了计算的方便，并不需要在和前面一样的麻烦，只有判断最后一步就可以m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);

输入及背包容量较小的结果（数据手动收入）:'F:\算法实验憧验^动态规划法乜已ro-□nel\Debug\^ero-onel.exe(Ctrl4-Shift4-特装物品的价值为:1243Thetimeis0.021特装物品的价值为:1243Thetimeis0.021J2)F:\算法实验\实验二动态规划法\zeroonel\Debug\zero-onel.exe测试结果入物&物6—龔71装71测试结果入物&物6—龔71装71包包请待24待24背背16斗..■■■・■56值为:1价号_b^59为59的编脊个值50量50大品出的价1重1曰粉□.1.1□nr^u-6-IZ7-T6-TT-T-TT-T0

T_Ln.B3.B3.B.B118244182441945419454207322073217778263501777826350Thetimeis0.062输入及背包容量较大的结果（数据由随机函数产生）:亘3F:\算法实验\实验二诙态规划法乜呂『09门elXDebug\zero-onel.exe100&0&0100278062785121408713529818193441228148662508?484217986128356451301164448146422613829180223882274601827029278062785121408713529818193441228148662508?484217986128356451301164448146422613829180223882274601827029228792311391411399606868502508425104193912031518237187962856030845100701916726933265731687618895265171776516445967831235642810582117821793830984262452556220394322276662068218833095323082295914850185381078022161098947015304127172928554922235516514104271336030496105822478621108281562458814863247981576994412554816690126061104116912594642843635292252449132676待装物品的重量为:1211631594143262780627051214087135298181934412281486625087484217986228792311391411283564513011644481464226138291802238822746018270291399606868502508425104193912031518237187962856030845100701916726933265731687618895265171776516445967831235642810582117821793830984262452556220394322276662068218833095323082295914850185381078022161098947015304127172928554922235516514104271336030496105822478621108281562458814863247981576994412554816690126061104116912594642843635292252449132676背包能装的最大的价值为:1000000背包装下的物品编号为：4243454G47485052S354555G575860G162636465666768G970717273747677787980818283848586878889909192949596979899100Thetimeis6.081

实验心得对于这一次的实验，利用动态规划的算法求解0-1背包问题，虽然课本上有函数的实现但是实验做起来还是有一定的难度的，毕竟我们追求的不是将代码敲出来而是真正掌握了这一个经典的算法实例。首先我是自己写了主函数，然后照着课本敲的代码,然后自己一步步分析代码中的不足的部分，加以完善，后来经过自己对于这个问题的理解，发现课本上的代码有一些不太容易理解的地方，就按照自己的理解进行了一些改变，最终实现了将自己的理解与代码完全融合，后来自己又仔细研究了一下书上的代码，发觉自己的代码效率不高，就有进行了改进，最终得到了较为满意的代码。不过在实验过程中也遇到了很多的问题，最主要的问题是经常出现中断，这使我很郁闷，不过好在在冋学的帮助下都顺利解决了，感觉很开心，然后由于要测试大数据，所以采用了随机生成函数，以及动态分配内存，学的利用到很多以前不太用到的知识，感觉棒棒的。实验比较观察上面三种不冋数据规模的输入，我们可以看到当物品的数量比较多的时候，算法是比较浪费时间的，其次是背包的容量也是一种限制性因素，而且采用随机生成函数有一点不好的就是生成的数据都是比较大的，有点不符合实际，我想在实际问题处理中应该采用的是读文件的方式输入的吧，不然采用手动输入，还是十分麻烦的。实验得分助教签名附录：完整代码//0-1背包问题，动态规划算法#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) //随机生成数组元素函数{inti;srand(time(0));for(i=1;i<=n;i++)input[i]=rand();//input[i]='\0';

intmain(){intc,n;coutvv"请输入背包的容量:cin>>c;coutvv"请输入物品的个数:cin>>n;//下标从1开始int//下标从1开始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];手动输入的代码部分******/*coutvv"待装物品的重量为："vvendl;for(i=1;iv=n;i++)cin>>w[i];coutvvendl;coutvv"待装物品的价值为："vvendl;for(i=1;iv=n;i++)cin>>v[i];coutvvendl;*/随机生成数据部分******ran(v,n);coutvv"待装物品的价值为："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; //计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();

Knapsack(v,w,c,n,m); //函数调用，求解0-1背包问题coutvv"背包能装的最大的价值为："vvm[l][c]vvendl;Traceback(m,w,c,n,x); //函数调用，构造最优解coutvv"背包装下的物品编号为："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);//显示运行时间for(i=0;ivn+l;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//没产生任何效益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