算法分析与设计-贪心算法

《算法分析与设计-贪心算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、专业课程实验报告课程名称:算法分析与设计开课学期：2014至2015学年第1学期专业：软件工程年级班级：2012级03班学生姓名：李明洋学号：222012321062053曹严元实验教师:计算机与信息科学学院软件学院实验项目名称贪心算法实验时间2014年门月14实验类型□验证性□设计性□综合性日「一、实验目的1.掌握贪心法的基本思想方法；2.了解适用于用贪心法求解的问题类型，并能设计相应贪心法算法；3.学握贪心算法复杂性分析方法分析问题复杂性。二、实验要求1.预习实验指导书及教材的有关内容，掌握贪心算法的基本思想；2.严格按照实验内容进行实验，培养良好的算法

2、设计和编程的习惯；3.认真听讲，服从安排，独立思考并完成实验。三、实验内容与设计(主要内容，操作步骤、算法描述或程序代码)实现背包问题的贪心算法procedureKNAPSACK(P,W,M,X,n)//P(l：n)和W(l；n)分别含有按P(i)/W(i)>P(i+l)/W(i+l)排序的n件物品的效益值和重SoM是背包的容量大小，而x(l：n)是解向量realP(l：n),W(l：n),X(l：n),M,cu；integeri,n；X-0//将解向量初始化为零cu—M//cu是背包剩余容量fori—1tondoifW(i)>cuthenexitendif

3、X(i)Tcu*-cu-W(i)repeatifiWnthenX(i)—cu/W(i)endifendGREEDY-KNAPSACKprocedureprini(G,)status*-"unseen”//T为空status[1]“treenode”//将1放入Tforeachodge(l,w)dostatus[w]*-"fringe”//找到T的邻接点dad[w]—1;//w通过1与T建立联系dist[w]—weight(1,w)//w到T的距离repeatwhilestatus[t]H“treenode"dopickafringeuwithmindistW

4、//选取到T最近的节点status[u]—“treenode”foreachedge(u,w)do修改w和T的关系repeatrepeat程序代码：#includeh>structgoodinfo{floatp;//物品效益floatw;//物品重量floatX;//物品该放的数量intflag;//物品编号}；//物品信息结构体voidInsertionsort@oodinfogoods[],intn){intj,i;for(j=2;j<=n;j++){goods[0]=goods[j];while(goods[0].p>goods[i

5、].p){goods[i+l]=goods[i];i—；}goods[i+l]=goods[0];}}//按物品效益，重量比值做升序排列voidbag(goodinfogoods[],floatM,intn){floatcu;inti,j;for(i=l;i<=n;i++)goods[i].X=0;cu=M;//背包剩余容量for(i=l;icu)//当该物品重量大与剩余容量跳出break;goods[i].X二1;cu二cu-goods[i].v;//确定背包新的剩余容量}if(i<=n)goods[i]・X=

6、cu/goods[i]・w;//该物品所要放的量for(j=2;j<=n;j++)goods[0]=goods[j];i=j-l；while(goods[0].flag

7、运用贪心法解背包问题

8、/z«endl;cout<<"

9、1，z«en

10、dl:intj;intn;floatM;goodinfo*goods;//定义一个指针while(j){cout«，z请输入物品的总数量：〃；cin»n;goods二newstructgoodinfo[n+1];//cout«，z请输入背包的最大容量：〃；cin»M;cout<

11、goods[i]・w;〃得出物品的效益,重量比cou