Java实验贪心算法,包含普通背包和贪心算法中的活动安排
- 格式：doc
- 大小：102.00 KB
- 文档页数：5
实验报告7
课程 数据结构与算法 实验名称 贪心策略 第 页
班级 11计本
学号 105032011130
姓名 风律澈
实验日期：2013年4月15日 报告退发 (订正 、 重做)
一、实验目的
掌握贪心策略的原理和应用。
二、实验环境
1、微型计算机一台
2、WINDOWS操作系统，Java SDK，Eclipse开发环境
三、实验内容
必做题：
1、编写程序，求解普通背包问题，要求输出背包所能容纳物品的最大价值(最优值)，及与该最大价值相应的装入背包中的每件物品信息。
2、设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si 四、实验步骤和结果 (附上代码和程序运行结果截图) 1、普通背包问题 //goods.class public class goods implements Comparable private static int 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(){ return e; } //输出设置// public void setuse(int u){ e=u; } //方法// public int compareTo(goods o){ if(this.value*o.weight>o.value*this.weight) return -1;//使用交叉相乘的方法避免除法，a/b?c/d=ad?bc if(this.value*o.weight return 0; } public String toString(){ return "物品编号"+this.id+" 物品重量"+this.weight+" 物品价值"+this.value+" 物品使用情况"+e; } } //NormalBag import java.util.ArrayList; import java.util.PriorityQueue; public class NormalBag { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub //初始化队列// PriorityQueue //定义暂存结果数组// ArrayList //初始化背包值// int c=10;//背包当前容量 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(); } else{ v+=c*t.getVW(); t.setuse(c); c=0; } place.add(t); } //输出结果// System.out.println(v); System.out.println(place); } //创建队列元素 private static PriorityQueue // TODO Auto-generated method stub 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 main(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 int[s.length];//定义标记选择过的活动数组 int count=0;//活动数量计数器 //开始选择// greedyselector(s,f,a); //输出// for(int i=0;i if(a[i]==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; a[0]=1;//最先的那个最优 int j=0; for(int i=1;i<=n;i++){ if(s[i]>=f[j]){ a[i]=1; j=i; } else a[i]=0; } } } 五、实验总结 (本次实验完成的情况，心得体会)
