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

《算法贪心算法----活动时间安排.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY算法设计与分析实验报告实验项目实验二实验类别验证性学生姓名王龙学生学号201400797完成日期2016-4-15指导教师刘振章实验成绩评阅日期评阅教师刘振章实验二：贪心算法【实验目的】深入理解贪心法的算法思想，应用贪心算法解决实际的算法问题。【实验性质】验证性实验。【实验要求】有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。求解安排尽量多项活动在该场地进行，即求A的

2、最大相容子集。设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下：i1234567891011s[i]130535688212f[i]4567891011121314将此表数据作为实现该算法的测试数据。【算法思想及处理过程】实验的算法思想：活动优先安排最早结束的项目，并且要求后一个活动与前一个活动相容，即sj≥fi时（j为后一个活动），最后输出安排尽可能多的相容活动。voidinput(inta[][3])：输入时间。通过函数中的for循环输入活动的开始时间和结束时间，并自动续上输入顺序编号。voidso

3、rt(inta[][3])：排序。通过二重for循环对结束时间进行比较，在通过一重for循环交换时间和序号。intgreed(inta[][3],intarr[][11][3],intm)：判断记录被选中的活动时间。本函数是本程序的核心：1、从第M个活动时间开始（利用主函数中的M，M是从0到11），通过for循环和if语句比较后一个活动的开始时间是否大于前一个活动的结束时间，如果如果大于，则用一个三维数组arr记录下了；然后换到下一个活动时间2、重复第1步，直到最后一个活动为止。【程序代码】#include

4、.h>voidinput(inta[][3]);//输入活动时间voidsort(inta[][3]);//排序voidoutput1(inta[][3]);//排序的结果输出intgreed(inta[][3],intarr[][11][3],intm);//判断记录被选中的活动时间voidoutput2(inta[][11][3],inty,intm);//输出最大的的活动时间intyi=0;intmain(){intarray[11][3];intarr[11][11][3]={0};intz,y,m,b[12]

5、={0};input(array);sort(array);printf("");output1(array);printf("");for(m=0;m<11;m++)b[m]=greed(array,arr,m);y=0;for(m=0;m<11;m++)if(y

6、or(i=0;i<11;i++){a[i][0]=i+1;printf("请输入第%d个活动的开始时间和结束时间:",i+1);for(j=1;j<3;j++)scanf("%d",&a[i][j]);}}voidsort(inta[][3]){inti,j,k,t;for(i=0;i<10;i++)for(j=0;j<10-i;j++)for(k=0;k<3;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;}}voidoutput1(

7、inta[][3]){inti,j;printf("按结束时间的升序排列如下：");for(i=0;i<11;i++){printf("原来序号%d的开始时间和结束时间：",a[i][0]);for(j=1;j<3;j++)printf("%d",a[i][j]);printf("");}}intgreed(inta[][3],intarr[][11][3],intm){inti,j,k,y=1;k=a[m][2];//for(i=0;i<3;i++)arr[yi][0][i]=a[m][i];//for(i=

8、m;i<11;i++){if(k<=a[i][1]){k=a[i][2];for(j=0;j<3;j++)arr[yi][y][j]=a[i][j];y++;}}yi++;returny;}voidoutput2(inta[][11][3],inty,intm){inti,j;for(i=0;i