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

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY 算法设计与分析 实 验 报 告 实验项目 实验二 实验类别 验证性 学生姓名 王龙 学生学号 201400797 完成日期 2016-4-15 指导教师 刘振章 实验成绩 评阅日期 评阅教师 刘振章 实验二：贪心算法 【】 【】 【】 …,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。求解安排尽量多项活动在该场地进行，即求A的最大相容子集。 设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下： i 1 2 3 4 5 6 7 8 9 10 11 s[i] 1 3 0 5 3 5 6 8 8 2 12 f[i] 4 5 6 7 8 9 10 11 12 13 14 将此表数据作为实现该算法的测试数据。 【 实验的算法思想 void input(int a[ ][3])：输入时间。 通过函数中的for循环输入活动的开始时间和结束时间，并自动续上输入顺序编号。 void sort (int a[ ][3])：排序。 通过二重for循环对结束时间进行比较，在通过一重for循环交换时间和序号。 int greed (int a[ ][3], int arr[][11][3], int m)：判断记录被选中的活动时间 。 本函数是本程序的核心：1、从第M个活动时间开始（利用主函数中的M，M是从0到11），通过for循环和if语句比较后一个活动的开始时间是否大于前一个活动的结束时间，如果如果大于，则用一个三维数组arr记录下了；然后换到下一个活动时间2、重复第1步，直到最后一个活动为止。 【程序代码】 # include stdio.h void input(int a[ ][3]); //输入活动时间 void sort (int a[ ][3]); //排序 void output1 (int a[ ][3]); //排序的结果输出 int greed (int a[ ][3], int arr[][11][3], int m); //判断记录被选中的活动时间 void output2 (int a[][11][3], int y,int m); //输出最大的的活动时间 int yi=0; int main () { int array[11][3]; int arr[11][11][3]={0}; int z, y, m, b[12]={0}; input (array); sort (array); printf (\n); output1 (array); printf (\n); for (m=0; m11; m++) b[m] = greed (array, arr, m); y = 0; for (m=0; m11; m++) if (y b[m]) { y = b[m]; z = m; } printf (安排活动时间的最大相容子集：\n); output2 (arr, y,z); return 0; } void input(int a[ ][3]) { int i, j; printf (请按提示操作!!! \n\n); for (i=0; i11; i++) { a[i][0]=i+1; printf (请输入第%d个活动的开始时间和结束时间:, i+1); for(j=1; j3; j++) scanf (%d, a[i][j]); } } void sort (int a[ ][3]) { int i, j, k, t; for (i=0; i10; i++) for (j=0; j10-i; j++) for (k=0; k3; k++) if (a[j][2] a[j+1][2]) { t = a[j][k]; a[j][k] = a[j+1][k]; a[j+1][k] = t; } } void output1 (int a[ ][3]) { int i, j; printf (按结束时间的升序排列如下：\n); for (i=0; i11; i++) { printf (原来序号%d的开始时间和结束时间 ：, a[i][0]); for (j=1; j3; j++) printf ( %d, a[i][j]); printf (\n); } } int greed (int