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

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

1、实验二：贪心算法【实验目的】深入理解贪心法的算法思想，应用贪心算法解决实际的算法问题。【实验性质】验证性实验。【实验要求】有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。求解安排尽量多项活动在该场地进行，即求A的最大相容子集。【程序代码】#includevoidinput(inta[][3]);//输入活动时间voidsort(inta[][3]);//排序voidoutput1(inta[][3]);//排序的结果输出intgreed(inta[][3],in

2、tarr[][50][3],intm);//判断记录被选中的活动时间voidoutput2(inta[][50][3],inty,intm);//输出最大的的活动时间intyi=0;intn;intmain(){intarray[50][3];intarr[50][50][3]={0};intz,y,m,b[12]={0};printf("活动总数量n(n<50)!!!");scanf("%d",&n);input(array);sort(array);printf("");output1(array);printf("");for(m=0;

3、m

4、i,j,k,t;for(i=0;ia[j+1][2]){t=a[j][k];a[j][k]=a[j+1][k];a[j+1][k]=t;}}voidoutput1(inta[][3]){inti,j;printf("按结束时间的升序排列如下：");for(i=0;i

5、");}}intgreed(inta[][3],intarr[][50][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=m;i

6、了原来序号为第%d活动，他的开始结束时间分别为：",a[m][i][0]);for(j=1;j<3;j++){printf("%d",a[m][i][j]);}printf("");}}法二#include#defineactive_num11//活动数#definetrue1         //记录被选的活动#definefalse0        //未被选择的活动intgreedySelector(ints[],intf[],intb[])// 算法{    b[0]=true;    intj=0;    inti=1;   

7、 intcount=1;    for(i=1;i<=active_num;i++)    {        if(s[i]>f[j])        {            b[i]=true;            j=i;            count++;        }        else        b[i]=false;    }    printf("activenumberis%d",count);    for(i=0;i

8、  printf("%d",i+1);    }