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

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY算法设计与分析实 验 报 告实验项目实验二实验类别验证性学生姓名王龙学生学号201400797完成日期2016-4-15指导教师刘振章实验成绩评阅日期评阅教师刘振章实验二：贪心算法【实验目的】深入理解贪心法的算法思想，应用贪心算法解决实际的算法问题。【实验性质】验证性实验。【实验要求】有n个活动的集合A=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。求解安排尽量多项活动在该场地进行，即求A的最大相容子集。设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下：i1234567891011si130535688212fi4567891011121314将此表数据作为实现该算法的测试数据。【算法思想及处理过程】实验的算法思想：活动优先安排最早结束的项目，并且要求后一个活动与前一个活动相容，即sjfi时（j为后一个活动），最后输出安排尽可能多的相容活动。void input(int a 3)：输入时间。 通过函数中的for循环输入活动的开始时间和结束时间，并自动续上输入顺序编号。void sort (int a 3)：排序。 通过二重for循环对结束时间进行比较，在通过一重for循环交换时间和序号。int greed (int a 3, int arr113, int m)：判断记录被选中的活动时间 。 本函数是本程序的核心：1、从第M个活动时间开始（利用主函数中的M，M是从0到11），通过for循环和if语句比较后一个活动的开始时间是否大于前一个活动的结束时间，如果如果大于，则用一个三维数组arr记录下了；然后换到下一个活动时间2、重复第1步，直到最后一个活动为止。【程序代码】# include void input(int a 3); /输入活动时间void sort (int a 3); /排序 void output1 (int a 3); /排序的结果输出int greed (int a 3, int arr113, int m); /判断记录被选中的活动时间 void output2 (int a113, int y,int m); /输出最大的的活动时间int yi=0;int main ()int array113;int arr11113=0;int z, y, m, b12=0;input (array);sort (array);printf (n);output1 (array);printf (n);for (m=0; m11; m+)bm = greed (array, arr, m);y = 0;for (m=0; m11; m+)if (y bm)y = bm;z = m;printf (安排活动时间的最大相容子集：n);output2 (arr, y,z);return 0;void input(int a 3) int i, j;printf (请按提示操作! nn);for (i=0; i11; 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; i10; i+)for (j=0; j10-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; i11; i+) printf (原来序号%d的开始时间和结束时间 ：, ai0);for (j=1; j3; j+)printf ( %d, aij);printf (n);int greed (int a 3, int arr113, int m) int i, j, k, y=1;k = am2;/for (i=0; i3; i+)arryi0i = ami;/for (i=m; i11; i+)if (k = ai1)k = ai2;for (j=0; j3; j+)arryiyj = aij;y+;yi+;return y;void output2 (int a113, int y,int m) int i, j;for (i=0; iy; i+)printf (选中了原来序号为第%d活动，他的开始结束时间分别为：, ami0);for (j=1; j3