贪心算法活动时间安排

1、实验二：贪心算法【实验目的】深入理解贪心法的算法思想，应用贪心算法解决实际的算法问题。【实验性质】验证性实验。【实验要求】有n个活动的集合A=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。求解安排尽量多项活动在该场地进行，即求A的最大相容子集。【程序代码】# include <stdio.h>void input(int a 3); /输入活动时间void sort (int a 3); /排序 void output1 (int a 3); /排序的结果输出int greed (int a 3, int arr503, int

2、 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(n<50)! nn");scanf ("%d", &n);input (array);sort (array);printf ("n");output1 (array);printf ("n"

3、;);for (m=0; m<n; m+)bm = greed (array, arr, m);y = 0;for (m=0; m<n; 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; i<n; i+)ai0=i+1;printf ("请输入第%d个活动的开始时间和结束时间:", i+1);for(j=1; j<3; j+)scanf

4、 ("%d", &aij);void sort (int a 3) int i, j, k, t;for (i=0; i<n-1; i+)for (j=0; j<n-1-i; j+)for (k=0; k<3; k+)if (aj2 > aj+12)t = ajk;ajk = aj+1k;aj+1k = t;void output1 (int a 3) int i, j;printf ("按结束时间的升序排列如下：n");for (i=0; i<n; i+) printf ("原来序号%d的开始时间和结束时

5、间 ：", ai0);for (j=1; j<3; 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; i<3; i+)arryi0i = ami;/for (i=m; i<n; i+)if (k <= ai1)k = ai2;for (j=0; j<3; j+)arryiyj = aij;y+;yi+;return y;void output2

6、(int a503, int y,int m) int i, j;for (i=0; i<y; i+)printf ("选中了原来序号为第%d活动，他的开始结束时间分别为：", ami0);for (j=1; j<3; j+)printf ("%d ", amij );printf ("n");法二#include <stdio.h>#define active_num 11 /活动数#define true 1        &#

7、160; /记录被选的活动#define false 0         /未被选择的活动int greedySelector(int s,int f,int b)/  算法    b0 = true;    int j = 0;    int i = 1;    int count = 1;    for(

8、i = 1;i <=active_num; i+ )            if(si > fj)                    bi = true;         &

9、#160;  j = i;            count+;                else        bi = false;      

10、60; printf("active number is %dn",count);    for(i=0;i<active_num;i+)            if(bi = 1)            printf("%d ",i+1);  

11、;      return 0;int main()         int i;        int start_timeactive_num;        int finish_timeactive_num;      &

12、#160; int booleanactive_num;         printf("please input the start timen");        for(i = 0; i < active_num; i+)              

13、;  scanf("%d",&start_timei);         printf("please input the finish timen");        for(i = 0; i < active_num; i+)