《java实验贪心算法包含普通背包和贪心算法中的活动安排》由会员分享，可在线阅读，更多相关《java实验贪心算法包含普通背包和贪心算法中的活动安排（5页珍藏版）》请在金锄头文库上搜索。
1、实验报告7课程 数据结构与算法 实验名称 贪心策略 第 页班级 11计本 学号 105032011130 姓名 风律澈 实验日期：2013年4月15日 报告退发 (订正 、 重做) 一、实验目的掌握贪心策略的原理和应用。二、实验环境1、微型计算机一台 2、WINDOWS操作系统，Java SDK，Eclipse开发环境三、实验内容 必做题：1、 编写程序，求解普通背包问题，要求输出背包所能容纳物品的最大价值(最优值)，及与该最大价值相应的装入背包中的每件物品信息。2、 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个
2、活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。编写程序，在所给的活动集合中选出最大的相容活动子集合。要求输出活动数量(即最优值)和最大相容活动子集中的每个活动(即最优解)。四、实验步骤和结果(附上代码和程序运行结果截图)1、 普通背包问题/goods.classpublic class goods implements Comparable private static i
3、nt ids=1;private int id;private int weight;private int value;private int use;/初始化对象/public goods(int w,int v)super();id=ids+;weight=w;value=v;use=0;/获取输出值/public float getVW()return this.value/this.weight;public int getw()return this.weight;public int getv()return this.value;public int getuse()retur
4、n this.use;/输出设置/public void setuse(int u)this.use=u;/方法/public int compareTo(goods o)if(this.value*o.weighto.value*this.weight) return -1;/使用交叉相乘的方法避免除法，a/b?c/d=ad?bcif(this.value*o.weighto.value*this.weight) return 1;return 0;public String toString()return 物品编号+this.id+ 物品重量+this.weight+ 物品价值+this
5、.value+ 物品使用情况+this.use;/NormalBagimport java.util.ArrayList;import java.util.PriorityQueue;public class NormalBag /* * param args */public static void main(String args) / TODO Auto-generated method stub/初始化队列/PriorityQueue pq=initpq();/定义暂存结果数组/ArrayList place=new ArrayList();/初始化背包值/int c=10;/背包当前
6、容量int v=0;/背包当前价值/开始放入物品/goods t;/设定暂存记录变脸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();elsev+=c*t.getVW();t.setuse(c);c=0;place.add(t);/输出结果/System.out.println(v);System.out.println(place);/创建队列元素private static
7、 PriorityQueue initpq() / TODO Auto-generated method stubPriorityQueuepq=new PriorityQueue();pq.offer(new goods(2,6);pq.offer(new goods(2,3);pq.offer(new goods(6,5);pq.offer(new goods(5,4);pq.offer(new goods(4,6);return pq;2. 活动安排问题public class GreedySelector /* * param args */public static void mai
8、n(String args) / TODO Auto-generated method stub/初始化/int s=1,3,0,5,3,5,6,8,8,2,12;/开始时间数组，已排序int f=4,5,6,7,8,9,10,11,12,13,14;/结束时间数组，已排序int a=new ints.length;/定义标记选择过的活动数组int count=0;/活动数量计数器/开始选择/greedyselector(s,f,a);/输出/for(int i=0;is.length;i+)/输出活动序号if(ai=1)System.out.print(活动+(i+1)+ );count+;System.out.println();System.out.print(活动总数量为：+count);/输出总活动数量private static void greedyselector(int s, int f, int a) / TODO Auto-generated method stub/贪心选择为，先结束的互动优先，这样剩余的时间达到最大，安排活动最多/int n=s.length-1;a0=1;/最先的那个最优int j=0;for(int i=1;i=fj)ai=1;j=i;elseai=0;五、实验总结(本次实验完成的情况，心得体会)
