贪心法解活动安排问题(计算机算法设计与分析)

1、实验报告课程名称:任课教师: 班 级: 姓 名:算法设计与分析张锦雄2007级1班蓝冠恒实验名称:专 业:学 号:完成日期:贪心法解活动安排问题计算机科学与技术2011年1月12日一、实验目的：掌握贪心法解活动安排问题的原理，并能够按其原理编程实现对输入的活动时间段进行 合理安排，加深对贪心法解活动安排问题的理解。二、主要实验内容及宴求1. 要求按贪心法求解问题；2. 要求读文本文件输入活动安排时间区间数据；3 要求显示结果。三、实验环境和操作系统:win7操作系统开发工具：eclipse3.4> jdkl.6开发语言：java四、实验结果与结论：（经调试正确的源程序和程序的运行结果）1

2、、源代码：package cn.lgh;import javaiobufferedreader;import javaiofilereader;import javaioioexception;import java.io.inputstreamreader;/ * *贪心法解活动安排问题。* author蓝冠恒*/public class greedyselector public int starttimes ; /活动起始时间点数组public int endtimes ;/活动结束时间点数组public boolean resultflags ; /被选j舌动标识数纟hpublic s

3、tring activregions =活动时间区间字符串public string result =纟占果字符串*构造方法*/public greedyselector()*构造方法* gparam starttimes* 活动起始吋间数组* gparam endtimes* 活动结束时间数组*/public greedyselector(int starttimes, int endtimes)thisstarttimes = starttimes;thisendtimes = endtimes;/贪心算法具体实现过程private int greedyselector ()int n =

4、 stdrttimes.length;resultflags0 = true;int j = 0;int count = 1;for (int i = 1; i < n; i+)if (starttimesi >= endtimesj)resultf1dgsi = true; j = 1;count+; else resultflagsi = false;return count;/按活动结朿时间非递减排序private void sort()int tmp;int n=starttimeslength;for(int i=0;i<n;i+)for(int j=0;j<

5、n;j+)if(j<n-l && endtimesj>endtimesj+1) tmp=endtimesj;endtimesj=endtimesj+1；endtimesj+1=tmp;tmp=starttimesj;starttimesj=starttimesj+1; starttimesj+1=tmp;/ * *从文件中获取被安排活动的时间段，并用贪心算法对其选择。* param filepath* 文件路径* throws ioexception*/public void greedyfromfile(string filepath) throws ioexce

6、ption string line;bufferedreader in = new bufferedreader(new filereader(filepath);line = in.readline() .replaceall(n n, n n);while (line != null) activregions += line;line = in.readline ();dogreedyact ion ();/ *从控制台中读取被安排活动的时间段，并用贪心算法对其选择。* gthrows exception*/public void greedyfromconsole() throws e

7、xception string input;final string form = " 5, 6、3, 210, 23"bufferedreader in = new bufferedreader(new inputstreamreader(system.in);do system, out .printin ( n请输入活动时间区间(退出请按数字键1),格式如：” + form); input = inreadline().trim(); while(inputequals(n n );if (input.equals(n1n) ) return;activregions

8、 = input;dogreedyact ion ();return;/ * *执行贪心法解活动安排具体动作。*/private void dogreedyaction()if (activregions = n n)return;string activities = ectivregions.split("、 n );int num = activities.length;starttimes = new intnum;endtimes = new intnum;resultf丄且gs = new booleannum;string strtmp;string region ;f

9、or (int i = 0; i < num; i+)strtmp = activitiesi;region = strtmp.split(h );starttimesi = integer.parseznt(region0 .replace(nn, n n); endtimes i = integer .parsein t (region 1 . replace ( n n ,f);sort () ; /排序greedyselector ();result=;for (int i = 0; i < resultflags.length; i+)if (resultflagsi)r

10、esult += ,f ,f + starttimes i + ,f, n + endtimes i + n > ,f;int index = result.lastlndexofc'、 n);result = result.substring(0, index);public static void main(string args) string input;greedyselector greedyselector = new greedyselector();bufferedreader in = new bufferedreader(new inputstreamrea

11、der(system.in);do try do system, out .printin ( ”n按数字键1从指定文件中的获取数据内容”);system, out .printin ( ”按数字键2从控制台输入数据内容”);system, out .printin (”按数字键3退出系统”);input = inreadline().trim(); while (! (input.equals("1") i i inputequals("2")| | input.equals ('* 3 ");if (input equals ( ”

12、3”)break;if (input.equals (''i" ) )system, out .printin ("请输入数据文件路径：”);input = inreadline()trim();try greedyselector.greedyfromfile(input); catch (ioexception e) e.printstacktrace ();continue; else try greedyselectorgreedyfromconsole(); catch (exception e) e.printstacktrace ();cont

13、inue;sys tem out pri nt in活动安扫p区间：nn + greedyselector. vregions); system out print in (”n 贪心法解活动安排结果：nh + greedyselec tor. resul t); catch (ioexception e) e.printstacktrace(); while (true);2、运行结果:|7| g r eed y s e i ecto r j a va= b outline x =戸g i problems javadoc(囤 dedarstion貝 console) )c 曙(| 園 &#

14、163;0j?| 凸旦j 戸<terminated> greedyselector java application e:installsoftwarejavajdkl.6binjavaw.exe (2011-1-13 下午07:48:59)按数字键一一-从指走文件中的获取数据内容按数字键2-一-从控制台输入数据内容按数字键3-一-退出系统1请输入数据文件路径：d： 3lcz zkz活动安排区间：5> 8、2, 6、3，10 > 6> 9、7, 11、1> 3、8 17 s 10> 16贪心法解活动安排结果：1, 3、5> s 、10， 16按数字键一 一从指走文件中的获取数据内容按数字键-一-从控制台输入数据内容按数字键3-一-退出系统?一.v亠请输入活动时间区间（退出请按数字键1）,格式如：5, 6、3, 2 x 10, 2310> 12、5> 8 x 9> 11 % 6> 10、7, 11 x3活动安排区间：10，12 x 5，8 x 9，116, 10 x 7, 111，3贪心法解活动安排结果：1, 3 、5, 8 、9, 11按数字键-一从指定文件中的获取数