01背包问题动态规划及贪心法实现docx.docx

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

2、t w,int c,int n,Type * m)int jMax = 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 = m

3、i+1c) xi = 0;Elsexi = 1;c -=wi;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 ，然后，依贪心选择策略，将尽可

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

5、其他物品 （2，3，n ），背包重量仍然 maxweight ；若物品 1 被 ， 就 关于最大背包重量 maxweight -w1 的 ， rmaxweight, maxweight -w1 剩余重量的背包 。2.源程序代码/* 划 0-1 背包 */#include#includeint 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;fo

6、r(i=0;i=n-1;i+)for(j=0;j=C;j+)if(j=0;i-)if(VijVi-1j)xi=1;j=j-wi;elsexi=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)

7、;printf(n 请分别输入物品的重量 :n);for(i=0;in;i+)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 Knaps

8、ack(int *v,int *w,int *x,int c,int 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,

9、20,30,40,30;int x= 0,0,0,0,0,0,0,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+) i

10、f(i=1)printf(%d,xi);elseprintf( %d,xi);printf(n);finish=clock();/ 取结束时间printf( 所需时间 %f msn,(finish-start);return 0;五程序运行结果动态规划 0-1 背包问题运行结果截图贪心法 0-1 背包问题结果及截图六实验结果分析动态规划求 0-1 背包问题可以得出最优解， 而用贪心法求 0-1 背包问题可能会得不到最优解。分析：对于 0-1 背包问题，贪心算法之所以不能得到最优解是因为在这种情况下，它无法保证最后能将背包装满， 部分闲置的背包空间， 使每公斤背包的价值降低了。 以上算法的时间复杂度和空间复杂度为 O(n*n) ，其中时间复杂度基本已经不能再优化了，但空间复杂度可以优化到 O(n) 。七结论动态规划算法具有最优子结构性质， 因此动态规划能得到最优解。 贪心算法中， 作出的每步贪心决策都无法改变， 因为贪心策略是由上一步的最优解推导下一步的最优解， 而上一部之前的最优解则不作保留。 由前面中的介绍， 可以知道贪心法正确的条件是： 每一步的最优解一定包含上一步的最优解 。