算法貪心算法----活動時間安排.doc

《算法貪心算法----活動時間安排.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY算法設(shè)計與分析實驗報告實驗項目實驗二實驗類別驗證性學(xué)生姓名王龍學(xué)生學(xué)號201400797完成日期2016-4-15指導(dǎo)教師劉振章實驗成績評閱日期評閱教師劉振章實驗二：貪心算法【實驗?zāi)康摹可钊肜斫庳澬姆ǖ乃惴ㄋ枷?，?yīng)用貪心算法解決實際的算法問題?！緦嶒炐再|(zhì)】驗證性實驗?！緦嶒炓蟆坑衝個活動的集合A={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。求解安排盡量多項活動在該場地進(jìn)行，即求A的

2、最大相容子集。設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的升序排列如下：i1234567891011s[i]130535688212f[i]4567891011121314將此表數(shù)據(jù)作為實現(xiàn)該算法的測試數(shù)據(jù)。【算法思想及處理過程】實驗的算法思想：活動優(yōu)先安排最早結(jié)束的項目，并且要求后一個活動與前一個活動相容，即sj≥fi時（j為后一個活動），最后輸出安排盡可能多的相容活動。voidinput(inta[][3])：輸入時間。通過函數(shù)中的for循環(huán)輸入活動的開始時間和結(jié)束時間，并自動續(xù)上輸入順序編號。voidso

3、rt(inta[][3])：排序。通過二重for循環(huán)對結(jié)束時間進(jìn)行比較，在通過一重for循環(huán)交換時間和序號。intgreed(inta[][3],intarr[][11][3],intm)：判斷記錄被選中的活動時間。本函數(shù)是本程序的核心：1、從第M個活動時間開始（利用主函數(shù)中的M，M是從0到11），通過for循環(huán)和if語句比較后一個活動的開始時間是否大于前一個活動的結(jié)束時間，如果如果大于，則用一個三維數(shù)組arr記錄下了；然后換到下一個活動時間2、重復(fù)第1步，直到最后一個活動為止?！境绦虼a】#include

4、.h>voidinput(inta[][3]);//輸入活動時間voidsort(inta[][3]);//排序voidoutput1(inta[][3]);//排序的結(jié)果輸出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個活動的開始時間和結(jié)束時間:",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("按結(jié)束時間的升序排列如下：");for(i=0;i<11;i++){printf("原來序號%d的開始時間和結(jié)束時間：",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