实验四 0-1背包问题.doc

南华大学实验名称：0-1背包问题学 院：计 算 机 学 院专业班级：本2010电气信息类03班 学 号：20104030342 姓 名： 谢志兴指导教师： 余颖日期： 2012 年 4 月 24 日实验四 “0-1”背包问题一、 实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对贪心算法、动态规划算法的理解。二、 实验内容:掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题的求解方法，并分析其优缺点。三、 实验题1. “0-1”背包问题的贪心算法2. “0-1”背包问题的动态规划算法说明：背包实例采用教材P132习题六的6-1中的描述。要求每种的算法都给出最大收益和最优解。四、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、 实验程序/*贪心算法*/#includeusing namespace std;int max(int a,int b) if(ab) return a; else return b;void ZeroOneBag(int *v,int *w,int *x,int c,int n, int m8100) int i,j; for(j=0;jc;j+) if(j=1;i-)/*控制物品的循环,从第i-1件到第1件*/ 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;/*mnc大于0吗?大于就是选了*/ return;int main() int i=0,n=7; int w=0,2,3,5,7,1,4,1; int v=0,10,5,15,7,6,18,3; int x=0,0,0,0,0,0,0,0; cout程序自带数据为：n编号 重量 收益endl; for (i=1;in;i+) couti wi viendl; int m=15; int array8100=0; ZeroOneBag(v,w,x,m,7,array); cout背包能装的最大收益为: array1mn贪心算法的解为: ; for(i=1;i=n;i+) if(i=1) coutxi; else cout xi; coutendl; return 0; /*动态规划算法*/#includeusing namespace std;int max(int a,int b) if(ab) return a; else return b;void ZeroOneBag(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=0;jwi;j+) mij=mi+1j; 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() int i=0,n=7; int w=0,2,3,5,7,1,4,1; int v=0,10,5,15,7,6,18,3; int x=0,0,0,0,0,0,0,0; cout程序自带数据为：n编号 重量 收益endl; for (i=0;in;i+) couti+1 wi+1 vi+1endl; int m=15; int array8100=0; ZeroOneBag(v,w,x,m,7,array); cout背包能装的最大收益为: array1mn最优解为: ; for(i=1;i=n;i+) if(i=1) coutxi; else cout xi; coutendl; return 0; 六、 实验结果贪心算法的实验结果：动态规划算法的实验结果：七、 实验分析解决0/1背包问题的方法有多种，最常用的有贪心法和动态规划法。其中贪心法不一定能得到问题的最优解，而动态规划法都能得到最优解。动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪心