背包问题（动态规划和贪心法实现）

1、算法设计与分析实验报告实验二 0-1背包问题院系： 班级： 计算机科学与技术学号： 姓名： 任课教师： 成绩：湘 潭 大 学2016年5月实验二 0-1背包问题1. 实验内容分别编程实现动态规划算法和贪心法求0-1背包问题的最优解，分析比较两种算法的时间复杂度并验证分析结果。二实验目的1、掌握动态规划算法和贪心法解决问题的一般步骤，学会使用动态规划和贪心法解决实际问题；2、理解动态规划算法和贪心法的异同及各自的适用范围。三. 算法描述/*动态规划 0-1背包问题算法如下*/TemplateVoid Knapsack(Type v,int w,int c,int n,Type * m)int j

2、Max = min(wn - 1,c);For(int j = 0;j = jMax;j+)mnj = 0;For(int j = wn;j 1;i-)jMax = min(wi - 1,c);For(int j = 0;j = jMax;j+) mij = mi+1j;For(int j = wi;j = w1) m1c = max(m1c,m2c-w1+v1);TemplateVoid Traceback(Type*m,int w,int c,int n,int x)for(int i =1 ;i n;i +)If(mic = mi+1c) xi = 0;Elsexi = 1;c -=wi

3、;xn = (mnc) ? 1:0;按上述算法Knapsack计算后m1c给出所要求的0-1背包问题的最优解。相应的最优解可由算法Traceback计算如下。如果m1c =m2c,则x1 = 0,否则x1 = 1。当x1=0时，由m2c继续构造最优解。当x1 = 1时，由m2c-w1继续构造最优解。以此类推，可构造出相应的最优解（x1,x2,.,xn），时间复杂性O(n2n)。/*贪心法 0-1背包问题*/首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物

4、品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。四. 算法实现1. 数据结构及函数说明在该问题中物品质量Wn和包所能承受的最大重量都是又用户自己任意定义的，在实现的过程中用到一个栈来实现。第i件物品的选择有两种可能：i.物品i被选择，这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后。继续其余物品的选择；ii.物品i不被选择，这种可能性仅当不包含物品i不满足条件的情况。现以第一个物品为例，当物品1不被选择，则问题转变为相对于其他物品（2，3，n），背包重量仍然为maxweight；若物品1被选择，问题就变为关于最大背包重量为maxweight-w1的问题，现设r

5、maxweight,maxweight-w1为剩余重量的背包问题。2. 源程序代码/*动态规划 0-1背包问题*/#include#include int V200200; int max(int a,int b) if(a=b) return a; else return b; int KnapSack(int n,int w,int v,int x,int C) int i,j; for(i=0;i=n;i+) Vi0=0; for(j=0;j=C;j+) V0j=0; for(i=0;i=n-1;i+) for(j=0;j=C;j+) if(j=0;i-) if(VijVi-1j) xi

6、=1; j=j-wi; else xi=0; printf(n选中的物品是:n); for(i=0;in;i+) printf(%d ,xi); printf(n); return Vn-1C; void main() double start,finish; start=clock(); int s; int w15; int v15; int x15; int n,i; int C; n=5; printf(背包的最大容量:); scanf(%d,&C); printf(输入物品个数:); scanf(%d,&n); printf(n请分别输入物品的重量:n); for(i=0;in;i+

7、) scanf(%d,&wi); printf(n请分别输入物品的价值:n); for(i=0;in;i+) scanf(%d,&vi); s=KnapSack(n,w,v,x,C); printf(nMax_V:); printf(%dn,s); finish=clock(); printf(所需时间 %f msn,(finish-start); /*贪心法 0-1背包问题*/#include#includeint max(int a,int b) if(ab)return a;elsereturn b;void Knapsack(int *v,int *w,int *x,int c,int

8、 n, int m8100) int i,j;for(j=0; jc; j+) if(j=1; i-) for(j=wi; j=c; j+)mij=max(mi+1j,mi+1j-wi+vi);for(i=1; in; i+) if(mic=mi+1c)xi=0;else xi=1;c=c-wi;xn=(mnc)?1:0;return;int main() double start,finish; start=clock();int i=0;int n=5;int w= 0,30,20,40,40,40;int v= 0,40,20,30,40,30;int x= 0,0,0,0,0,0,0,

9、0;printf(背包的最大容量：100n);printf(物品个数为：5n);printf(物品重量分别为:);for (i=1; i=n; i+)printf(%d ,wi);printf(n物品价值分别为:);for (i=1; i=n; i+)printf(%d ,vi);int m=100;int array8100= 0;Knapsack(v,w,x,m,7,array);printf(nMAX_V: %dn,array1m);printf(选择的物品: );for(i=1; i=n; i+) if(i=1)printf(%d,xi);elseprintf( %d,xi);printf(n);finish=clock();/取结束时间printf(所需时间 %f msn,(finish-start);return 0;5 程序运行结果动态规划 0-1背包问题运行结果截图贪心法 0-1背包问题结果及截图6 实验结果分析动态规划求0-1背包问题可以得出最优解，而用贪心法求0-1背包问题可能会得不到最优解。分析：对于0-1背包问题，贪心算法之所以不能得到最优解是因为在这种情况下，它无法保证最后能将背包装满，部分闲置的背包空间，使每公斤背包的价值降低了。以上算法的时间复杂度和空间复杂度为O(n*n)，其中时间复杂度基本已经不能再