连续背包问题.doc

广东金融学院实验报告课程名称：算法设计与分析课程设计实验编号及实验名称实验五 贪心算法系 别应用数学系姓 名许夏梦学 号071612117班级0716121实验地点新电605实验日期2009-10-28实验时数2指导教师骆世广同组其他成员成绩一、 实验目的及要求1、 明确连续背包问题的概念；2、 利用贪心算法解决连续背包问题；3、 通过本例熟悉贪心算法在程序设计中的应用方法。二、 实验环境及相关情况（包含使用软件、实验设备、主要仪器及材料等）使用软件：C+软件；使用实验设备：计算机：Intel(R);Pentium(R) 4 CPU 2.80GHz;2.79 GHz,0.99 GB 的内存；使用系统：Microsoft Windows XP;Professional;版本 2002；Service Pack 2.三、 实验内容及步骤（包含简要的实验步骤流程）实验内容：已知n个物体和1个背包，其中物体i有重量wi和价值vi，背包承重量为W。求一装载方案，要求在不超过背包负重的前提下，背包中装入的物品价值最大。很明显，如果，则最优解就是装入全部物体，因此下面假设。注：连续背包问题中的物体可以任意分割，即部分装入背包。四、 实验结果（包括程序或图表、结论陈述、数据记录及分析等，可附页）实验结果如下（程序见附录四-1）：五、 实验总结（包括心得体会、问题回答及实验改进意见，可附页） 通过在计算机实现贪心算法的背包问题，对贪心算法有了较好的理解。实验是对书本理解一种很好的方法，在实验前，对贪心算法理解不深，也有点乱。通过有趣的背包问题在程序上实现算法，学习起来效果比之前好很多，通过调试可以知道自己想法的不足，通过不断的改进，促进算法设计水平的提高。六、 教师评语附四-1程序代码：#include #include using namespace std; struct goodinfo float p; /物品效益 float w; /物品重量 float X; /物品该放的数量 int flag; /物品编号 ;/物品信息结构体void Insertionsort(goodinfo goods,int n) int j,i; for(j=2;jgoodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; void bag(goodinfo goods,float M,int n) float cu; int i,j; for(i=1;i=n;i+) goodsi.X=0; cu=M; /背包剩余容量 for(i=1;icu)/当该物品重量大与剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w;/确定背包新的剩余容量 if(i=n) goodsi.X=cu/goodsi.w;/该物品所要放的量 for(j=2;j=n;j+) /*按物品编号做降序排列*/ goods0=goodsj; i=j-1; while (goods0.flaggoodsi.flag) goodsi+1=goodsi; i-; goodsi+1=goods0; cout最优解为:endl; for(i=1;i=n;i+) cout第i件物品要放:; coutgoodsi.Xendl; void main() int j,n; float M; goodinfo *goods;/定义一个指针 while(j) coutn; goods=new struct goodinfo n+1;/ coutM; coutendl; int i;for(i=1;i=n;i+) goodsi.flag=i; cout请输入第igoodsi.w; cout请输入第igoodsi.p;goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比 coutendl; Insertionsort