《贪心算法解活动安排实验报告.pdf》由会员分享，可在线阅读，更多相关《贪心算法解活动安排实验报告.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验 3 贪心算法解活动安排问题 一、实验要求 1要求按贪心法求解问题；2要求读文本文件输入活动安排时间区间数据；3要求显示结果。二、实验仪器和软件平台 仪器：带 usb 接口微机 软件平台：WIN-XP +VC+三、源程序#include#include#include#include#define N 50#define TURE 1#define FALSE 0 int sN;/*开始时间*/int fN;/*结束时间*/int AN;/*用 A 存储所有的*/int Partition(int*b,int*a,int p,int r);void QuickSort(int*b,int*
2、a,int p,int r);void GreedySelector(int n,int*s,int*f,int*A);int main()int n=0,i;while(n50)printf(n);printf(请输入活动的个数,n=);scanf(%d,&n);if(n50)printf(请输入小于 50 的数!);printf(n 请分别输入开始时间 si和结束时间 fi:nn);for(i=1;i=n;i+)printf(s%d=,i,i);scanf(%d,&si);printf(f%d=,i,i);scanf(%d,&fi);printf(n);QuickSort(s,f,1,n)
3、;/按结束时间非减序排列 printf(按结束时间非减序排列如下:n);/*输出排序结果*/printf(n 序号t 开始时间 结束时间n);printf(-n);for(i=1;i=n;i+)printf(%dt%dt%dn,i,si,fi);printf(-n);GreedySelector(n,s,f,A);/贪心算法实现活动安排 printf(安排的活动序号依次为：);for(i=1;i%d,i,si,fi);printf(n);system(pause);return 0;/快速排序 void QuickSort(int*b,int*a,int p,int r)int q;if(pr
4、)q=Partition(b,a,p,r);QuickSort(b,a,p,q-1);/*对左半段排序*/QuickSort(b,a,q+1,r);/*对右半段排序*/产生中间数 int Partition(int*b,int*a,int p,int r)int k,m,y,i=p,j=r+1;int x=ap;y=bp;while(1)while(a+ix);if(i=j)break;else k=ai;ai=aj;aj=k;m=bi;bi=bj;bj=m;ap=aj;bp=bj;aj=x;bj=y;return j;/贪心算法实现活动安排 void GreedySelector(int n
5、,int*s,int*f,int*A)/用集合 A 来存储所选择的活动 A1=TURE;/默认从第一次活动开始执行 int j=1;/j 记录最近一次加入到 A 中的活动 for(int i=2;i=fj)Ai=TURE;/当 Ai=TURE 时，活动 i 在集合 A 中 j=i;else Ai=FALSE;四、运行结果 五、实验小结 贪心算法总是做出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。