算法设计(eclipse编写贪心算法设计活动安排)

《算法设计(eclipse编写贪心算法设计活动安排)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、陕西师大计科院2009级《算法设计与分析》课程论文集算法设计（贪心算法解决活动安排）设计者：朱亚君贪心算法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。图1贪心算法的计算过程图若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。 贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结

2、论可以用数学归纳法证明。-3-陕西师大计科院2009级《算法设计与分析》课程论文集附录：贪心算法的实现具体程序如下：//贪心算法实现代码n为活动个数s为活动开始起始时间队列f为活动结束队列A为已选入集合importjava.util.Scanner;publicclassa{/***@paramargs*/staticvoidGreedySelector(ints[],intf[],booleanA[]){//第一个活动为结束时间最早进入选入队列intn=s.length;A[1]=true;intj=2;for(

3、inti=2;i=f[j]){A[i]=true;j=i;}elseA[i]=false;}}staticvoidpaixu(ints[],intf[])//进行以结束时间的大小排序{intn=s.length;intm;for(inti=0;if[j+1]){m=f[j];f[j]=f[j+1];f[j+1]=m;//终止时间如果前一个大于后一个就交换位置-3-陕西师大计科院2009级《算法设计与分析》课程论

4、文集m=s[j];s[j]=s[j+1];s[j+1]=m;//起始时间也同时进行交换位置}}}staticvoidOutput(booleana[],ints[],intf[]){intt=0;System.out.println("可以安排的活动有以下几个！");for(inti=0;i

5、),");t++;}}System.out.println("；最多可以安排的活动是"+t+"个。");}publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubScannerin=newScanner(System.in);System.out.print("请输入有几场活动！");intn=in.nextInt();ints[]=newint[n+1];System.out.println("请输入每场活动的开始时间（用空格隔开，以回车结

6、束）");for(inti=1;i<=n;i++)s[i]=in.nextInt();intf[]=newint[n+1];System.out.print("请输入每场活动的结束时间（用空格隔开，一回车结束）");for(intj=1;j<=n;j++)f[j]=in.nextInt();booleana[]=newboolean[12];paixu(s,f);GreedySelector(s,f,a);Output(a,s,f);}}-3-