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

算法设计（贪心算法解决活动安排）设计者：朱亚君贪心算法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。图1贪心算法的计算过程图若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。附录：贪心算法的实现具体程序如下：/ 贪心算法实现代码 n为活动个数 s为活动开始起始时间队列 f为活动结束队列 A为已选入集合import java.util.Scanner;public class a /* * param args */static void GreedySelector(int s,int f,boolean A)/第一个活动为结束时间最早进入选入队列int n=s.length; A1=true; int j=2;for(int i=2;i=fj)Ai=true; j=i; else Ai=false;static void paixu(int s,int f)/进行以结束时间的大小排序int n=s.length;int m;for(int i=0;in;i+)for(int j=i;jfj+1)m=fj;fj=fj+1;fj+1=m;/终止时间如果前一个大于后一个就交换位置m=sj;sj=sj+1;sj+1=m;/起始时间也同时进行交换位置static void Output(boolean a,int s,int f)int t=0;System.out.println(可以安排的活动有以下几个！);for(int i=0;is.length;i+)if(ai)System.out.print();System.out.print(si+,);System.out.print(fi);System.out.print(),);t+;System.out.println(；最多可以安排的活动是+t+个。);public static void main(String args) / TODO Auto-generated method stubScanner in=new Scanner(System.in);System.out.print(请输入有几场活动！);int n=in.nextInt();int s=new intn+1;System.out.println(请输入每场活动的开始时间（用空格隔开，以回车结束）);for(int i=1;i=n;i+)si=in.nextInt();int f=new intn+1;System.out.print(请输入每场活动的结束时间（用空格隔开，一回车结束）);for(int j=1;j=n;j+)fj=in.nextInt();bool