资源描述:
《实验四 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;j3、从第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;i4、*/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;j6、=1;i--){for(j=0;j7、[]={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<