Java实验贪心算法,包含普通背包和贪心算法中的活动安排.doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《Java实验贪心算法,包含普通背包和贪心算法中的活动安排.doc》由会员分享,可在线阅读,更多相关《Java实验贪心算法,包含普通背包和贪心算法中的活动安排.doc(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、实验报告7课程 数据结构与算法 实验名称 贪心策略 第 页班级 11计本 学号 0 姓名 风律澈 实验日期:2013年4月15日 报告退发 (订正 、 重做) 一、实验目的掌握贪心策略的原理和应用。二、实验环境1、微型计算机一台 2、WINDOWS操作系统,Java SDK,Eclipse开发环境三、实验内容 必做题:1、 编写程序,求解普通背包问题,要求输出背包所能容纳物品的最大价值(最优值),及与该最大价值相应的装入背包中的每件物品信息。2、 设有n个活动的集合E=1,2,n,其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用
2、该资源的起始时间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 int ids=1;pr
3、ivate 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 this.use;
4、/输出设置/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.value+ 物品使
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Java 实验 贪心 算法 包含 普通 背包 中的 活动 安排
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内