Java实验贪心算法,包含普通背包和贪心算法中的活动安排.doc

《Java实验贪心算法,包含普通背包和贪心算法中的活动安排.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验报告7课程数据结构与算法实验名称贪心策略第页班级11计本学号0姓名风律澈实验日期：2013年4月15日报告退发(订正、重做)一、实验目的掌握贪心策略的原理和应用。二、实验环境1、微型计算机一台2、WINDOWS操作系统，JavaSDK，Eclipse开发环境三、实验内容必做题：1、编写程序，求解普通背包问题，要求输出背包所能容纳物品的最大价值(最优值)，及与该最大价值相应的装入背包中的每件物品信息。2、设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该

2、资源的起始时间si和一个结束时间fi,且si{privates

3、taticintids=1;privateintid;privateintweight;privateintvalue;privateintuse;//初始化对象//publicgoods(intw,intv){super();id=ids++;weight=w;value=v;use=0;}//获取输出值//publicfloatgetVW(){returnthis.value/this.weight;}publicintgetw(){returnthis.weight;}publicintgetv(){returnthis.value;}publicintg

4、etuse(){returnthis.use;}//输出设置//publicvoidsetuse(intu){this.use=u;}//方法//publicintcompareTo(goodso){if(this.value*o.weight>o.value*this.weight)return-1;//使用交叉相乘的方法避免除法，a/b?c/d=ad?bcif(this.value*o.weight

5、+"物品重量"+this.weight+"物品价值"+this.value+"物品使用情况"+this.use;}}//NormalBagimportjava.util.ArrayList;importjava.util.PriorityQueue;publicclassNormalBag{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstub//初始化队列//PriorityQueuepq=initpq();//定义暂存结果数组//Arra

6、yListplace=newArrayList();//初始化背包值//intc=10;//背包当前容量intv=0;//背包当前价值//开始放入物品//goodst;//设定暂存记录变脸while(true){//设定借宿条件//if(c==0)break;if(pq.isEmpty())break;//取出替换元素//t=pq.poll();//开始比较//if(t.getw()<=c){v+=t.getv();t.setuse(t.getw());c-=t.getw();}else{v+=c*t.getVW();t.setuse

7、(c);c=0;}place.add(t);}//输出结果//System.out.println(v);System.out.println(place);}//创建队列元素privatestaticPriorityQueueinitpq(){//TODOAuto-generatedmethodstubPriorityQueuepq=newPriorityQueue();pq.offer(newgoods(2,6));pq.offer(newgoods(2,3));pq.offer(newgoods(6,5));pq.

8、offer(newgoo