实验四 0-1背包问题

《实验四 0-1背包问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南华大学实验名称：0-1背包问题学    院：计算机学院专业班级：本2010电气信息类03班 学     号：20104030342 姓    名：    谢志兴指导教师：余颖日期：2012年4月24日实验四“0-1”背包问题一、实验目的与要求熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划算法的理解。二、实验内容:掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题的求解方法，并分析其优缺点。三、实验题1.“0-1”背包问题的贪心算法2.“0-1”背包问题的动态规划算法说明：背包实例采用教材P132习题六

2、的6-1中的描述。要求每种的算法都给出最大收益和最优解。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序/*贪心算法*/#includeusingnamespacestd;intmax(inta,intb){if(a>b)returna;elsereturnb;}voidZeroOneBag(int*v,int*w,int*x,intc,intn,intm[8][100]){inti,j;for(j=0;j

3、从第n件物品开始，如果放不下*/m[n][j]=0;else/*如果放的下*/m[n][j]=v[n];}for(i=n-1;i>=1;i--)/*控制物品的循环,从第i-1件到第1件*/{for(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;i

4、*/return;}intmain(){inti=0,n=7;intw[]={0,2,3,5,7,1,4,1};intv[]={0,10,5,15,7,6,18,3};intx[]={0,0,0,0,0,0,0,0};cout<<"程序自带数据为："<<"编号重量收益"<

5、y[1][m]<<"贪心算法的解为:";for(i=1;i<=n;i++){if(i==1)cout<usingnamespacestd;intmax(inta,intb){if(a>b)returna;elsereturnb;}voidZeroOneBag(int*v,int*w,int*x,intc,intn,intm[8][100]){inti,j;for(j=0;j

6、=1;i--){for(j=0;j

7、[]={0,2,3,5,7,1,4,1};intv[]={0,10,5,15,7,6,18,3};intx[]={0,0,0,0,0,0,0,0};cout<<"程序自带数据为："<<"编号重量收益"<

8、=n;i++){if(i==1)cout<