贪心算法解活动安排实验报告

实验3贪心算法解活动安排问题一、实验要求1．要求按贪心法求解问题；2．要求读文本文件输入活动安排时间区间数据；3．要求显示结果。二、实验仪器和软件平台仪器：带usb接口微机软件平台：WIN-XP+VC++6.0三、源程序#includestdafx.h#includestdio.h#includestdlib.h#includealgorithm#defineN50#defineTURE1#defineFALSE0ints[N];/*开始时间*/intf[N];/*结束时间*/intA[N];/*用A存储所有的*/intPartition(int*b,int*a,intp,intr);voidQuickSort(int*b,int*a,intp,intr);voidGreedySelector(intn,int*s,int*f,int*A);intmain(){intn=0,i;while(n=0||n50){printf(\n);printf(请输入活动的个数,n=);scanf(%d,&n);if(n=0)printf(请输入大于零的数!);elseif(n50)printf(请输入小于50的数!);}printf(\n请分别输入开始时间s[i]和结束时间f[i]:\n\n);for(i=1;i=n;i++){printf(s[%d]=,i,i);scanf(%d,&s[i]);printf(f[%d]=,i,i);scanf(%d,&f[i]);printf(\n);}QuickSort(s,f,1,n);//按结束时间非减序排列printf(按结束时间非减序排列如下:\n);/*输出排序结果*/printf(\n序号\t开始时间结束时间\n);printf(-------------------------\n);for(i=1;i=n;i++)printf(%d\t%d\t%d\n,i,s[i],f[i]);printf(-------------------------\n);GreedySelector(n,s,f,A);//贪心算法实现活动安排printf(安排的活动序号依次为：);for(i=1;i=n;i++){if(A[i])printf(\n%d%d--%d,i,s[i],f[i]);}printf(\n);system(pause);return0;}//快速排序voidQuickSort(int*b,int*a,intp,intr){intq;if(pr){q=Partition(b,a,p,r);QuickSort(b,a,p,q-1);/*对左半段排序*/QuickSort(b,a,q+1,r);/*对右半段排序*/}}//产生中间数intPartition(int*b,int*a,intp,intr){intk,m,y,i=p,j=r+1;intx=a[p];y=b[p];while(1){while(a[++i]x);while(a[--j]x);if(i=j)break;else{k=a[i];a[i]=a[j];a[j]=k;m=b[i];b[i]=b[j];b[j]=m;}}a[p]=a[j];b[p]=b[j];a[j]=x;b[j]=y;returnj;}//贪心算法实现活动安排voidGreedySelector(intn,int*s,int*f,int*A){//用集合A来存储所选择的活动A[1]=TURE;//默认从第一次活动开始执行intj=1;//j记录最近一次加入到A中的活动for(inti=2;i=n;i++){//f[j]为当前集合A中所有活动的最大结束时间//活动i的开始时间不早于最近加入到集合A中的j的时间f[j]if(s[i]=f[j]){A[i]=TURE;//当A[i]=TURE时，活动i在集合A中j=i;}elseA[i]=FALSE;}}四、运行结果五、实验小结贪心算法总是做出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。