贪心算法----活动时间安排

实验二：贪心算法【实验目的】深入理解贪心法的算法思想，应用贪心算法解决实际的算法问题。【实验性质】验证性实验。【实验要求】有n个活动的集合A=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。求解安排尽量多项活动在该场地进行，即求A的最大相容子集。【程序代码】# include void input(int a 3); /输入活动时间void sort (int a 3); /排序 void output1 (int a 3); /排序的结果输出int greed (int a 3, int arr503, int m); /判断记录被选中的活动时间 void output2 (int a503, int y,int m); /输出最大的的活动时间int yi=0;int n;int main ()int array503; int arr50503=0;int z, y, m, b12=0;printf (活动总数量n(n50)! nn);scanf (%d, &n);input (array);sort (array);printf (n);output1 (array);printf (n);for (m=0; mn; m+)bm = greed (array, arr, m);y = 0;for (m=0; mn; m+)if (y bm)y = bm;z = m;printf (安排活动时间的最大相容子集：n);output2 (arr, y,z);return 0;void input(int a 3) int i, j;for (i=0; in; i+)ai0=i+1;printf (请输入第%d个活动的开始时间和结束时间:, i+1);for(j=1; j3; j+)scanf (%d, &aij);void sort (int a 3) int i, j, k, t;for (i=0; in-1; i+)for (j=0; jn-1-i; j+)for (k=0; k aj+12)t = ajk;ajk = aj+1k;aj+1k = t;void output1 (int a 3) int i, j;printf (按结束时间的升序排列如下：n);for (i=0; in; i+) printf (原来序号%d的开始时间和结束时间 ：, ai0);for (j=1; j3; j+)printf ( %d, aij);printf (n);int greed (int a 3, int arr503, int m) int i, j, k, y=1;k = am2;/for (i=0; i3; i+)arryi0i = ami;/for (i=m; in; i+)if (k = ai1)k = ai2;for (j=0; j3; j+)arryiyj = aij;y+;yi+;return y;void output2 (int a503, int y,int m) int i, j;for (i=0; iy; i+)printf (选中了原来序号为第%d活动，他的开始结束时间分别为：, ami0);for (j=1; j3; j+)printf (%d , amij );printf (n);法二#include #define active_num 11 /活动数#define true 1 /记录被选的活动#define false 0 /未被选择的活动int greedySelector(int s,int f,int b)/ 算法b0 = true;int j = 0;int i = 1;int count = 1;for(i = 1;i fj)bi = true;j = i;count+;elsebi = false;printf(active number is %dn,count);for(i=0;iactive_num;i+)if(bi = 1)printf(%d ,i+1);return 0;int main()int i;int start_timeactive_num;int finish_timeactive_num;int booleanactive_num;printf(please input the start timen);for(i = 0; i active_num; i+)scanf(%d,&start_timei);printf(please input the finish timen);for(i =