0-1背包问题(动态规划和贪心法实现)

算法设计与分析实验报告实验二0-1背包问题湘潭大学2016年5月院系：班级：计算机科学与技术学号：姓名：任课教师：成绩：2实验二0-1背包问题一.实验内容分别编程实现动态规划算法和贪心法求0-1背包问题的最优解，分析比较两种算法的时间复杂度并验证分析结果。二．实验目的1、掌握动态规划算法和贪心法解决问题的一般步骤，学会使用动态规划和贪心法解决实际问题；2、理解动态规划算法和贪心法的异同及各自的适用范围。三.算法描述/*动态规划0-1背包问题算法如下*/TemplateclassTypeVoidKnapsack(Typev,intw,intc,intn,Type**m){intjMax=min(w[n]-1,c);For(intj=0;j=jMax;j++){m[n][j]=0;}For(intj=w[n];j=c;j++){m[n][j]=v[n];}For(inti=n-1;i1;i--){jMax=min(w[i]-1,c);For(intj=0;j=jMax;j++)m[i][j]=m[i+1][j];For(intj=w[i];j=c;j++)min[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];If(c=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}TemplateclassTypeVoidTraceback(Type**m,intw,intc,intn,intx){for(inti=1;in;i++)If(m[i][c]==m[i+1][c])x[i]=0;Else{x[i]=1;c-=w[i];}x[n]=(m[n][c])?1:0;3}按上述算法Knapsack计算后m[1][c]给出所要求的0-1背包问题的最优解。相应的最优解可由算法Traceback计算如下。如果m[1][c]=m[2][c],则x1=0,否则x1=1。当x1=0时，由m[2][c]继续构造最优解。当x1=1时，由m[2][c-w1]继续构造最优解。以此类推，可构造出相应的最优解（x1,x2,...,xn），时间复杂性O(n2^n)。/*贪心法0-1背包问题*/首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。四.算法实现1.数据结构及函数说明在该问题中物品质量W[n]和包所能承受的最大重量都是又用户自己任意定义的，在实现的过程中用到一个栈来实现。第i件物品的选择有两种可能：i.物品i被选择，这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后。继续其余物品的选择；ii.物品i不被选择，这种可能性仅当不包含物品i不满足条件的情况。现以第一个物品为例，当物品1不被选择，则问题转变为相对于其他物品（2，3，……，n），背包重量仍然为maxweight；若物品1被选择，问题就变为关于最大背包重量为maxweight-w[1]的问题，现设r{maxweight,maxweight-w[1]}为剩余重量的背包问题。2.源程序代码/*动态规划0-1背包问题*/#includestdio.h#includetime.hintV[200][200];intmax(inta,intb){if(a=b)returna;elsereturnb;}intKnapSack(intn,intw[],intv[],intx[],intC){inti,j;4for(i=0;i=n;i++)V[i][0]=0;for(j=0;j=C;j++)V[0][j]=0;for(i=0;i=n-1;i++)for(j=0;j=C;j++)if(jw[i])V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);j=C;for(i=n-1;i=0;i--){if(V[i][j]V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}printf(\n选中的物品是:\n);for(i=0;in;i++)printf(%d,x[i]);printf(\n);returnV[n-1][C];}voidmain(){doublestart,finish;start=clock();ints;intw[15];intv[15];intx[15];intn,i;intC;n=5;5printf(背包的最大容量:);scanf(%d,&C);printf(输入物品个数:);scanf(%d,&n);printf(\n请分别输入物品的重量:\n);for(i=0;in;i++)scanf(%d,&w[i]);printf(\n请分别输入物品的价值:\n);for(i=0;in;i++)scanf(%d,&v[i]);s=KnapSack(n,w,v,x,C);printf(\nMax_V:);printf(%d\n,s);finish=clock();printf(所需时间%fms\n,(finish-start));}/*贪心法0-1背包问题*/#includestdio.h#includetime.hintmax(inta,intb){if(ab)returna;elsereturnb;}voidKnapsack(int*v,int*w,int*x,intc,intn,intm[8][100]){inti,j;for(j=0;jc;j++){if(jw[n])m[n][j]=0;elsem[n][j]=v[n];}for(i=n-1;i=1;i--){6for(j=w[i];j=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}for(i=1;in;i++){if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c=c-w[i];}}x[n]=(m[n][c])?1:0;return;}intmain(){doublestart,finish;start=clock();inti=0;intn=5;intw[]={0,30,20,40,40,40};intv[]={0,40,20,30,40,30};intx[]={0,0,0,0,0,0,0,0};printf(背包的最大容量：100\n);printf(物品个数为：5\n);printf(物品重量分别为:);for(i=1;i=n;i++){printf(%d,w[i]);}printf(\n物品价值分别为:);for(i=1;i=n;i++){printf(%d,v[i]);}7intm=100;intarray[8][100]={0};Knapsack(v,w,x,m,7,array);printf(\nMAX_V:%d\n,array[1][m]);printf(选择的物品:);for(i=1;i=n;i++){if(i==1)printf(%d,x[i]);elseprintf(%d,x[i]);}printf(\n);finish=clock();//取结束时间printf(所需时间%fms\n,(finish-start));return0;}五．程序运行结果动态规划0-1背包问题运行结果截图8贪心法0-1背包问题结果及截图六．实验结果分析动态规划求0-1背包问题可以得出最优解，而用贪心法求0-1背包问题可能会得不到最优解。分析：对于0-1背包问题，贪心算法之所以不能得到最优解是因为在这种情况下，它无法保证最后能将背包装满，部分闲置的背包空间，使每公斤背包的价值降低了。以上算法的时间复杂度和空间复杂度为O(n*n)，其中时间复杂度基本已经不能再优化了，但空间复杂度可以优化到O(n)。七．结论动态规划算法具有最优子结构性质，因此动态规划能得到最优解。贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。由前面中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。