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

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

1、詢處矩車工處舉院HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY占冬與信息工*峑算法投廿與分析實驗報告實驗項目實驗二實驗類別驗證性學生姓名王龍學生學號201400797完成日期2016-4-15指導教師劉振章實驗成績評閱日期評閱教師劉振章實驗二：貪心算法【實驗目的】深入理解貪心法的算法思想，應用貪心算法解決實際的算法問題?！緦嶒炐再|(zhì)】驗證性實驗?！緦嶒炓蟆坑衝個活動的集合A二｛1,2,..」｝,其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。求解安排盡量多項活動在該場地進行，即

2、求A的最大相容子集。設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的升序排列如下:■11234567891011s[i]130535688212f[i]4567891011121314將此表數(shù)據(jù)作為實現(xiàn)該算法的測試數(shù)據(jù)?！舅惴ㄋ枷爰疤幚磉^程】實驗的算法思想：活動優(yōu)先安排最早結(jié)束的項目，并且要求后一個活動與前一個活動相容，即sjNfi時(j為后一個活動)，最后輸出安排盡可能多的相容活動。voidinput(inta[][3J)：輸入時間。通過函數(shù)中的for循環(huán)輸入活動的開始時間和結(jié)束時間，并自動續(xù)上輸入順序編號。voidsort(intalJ

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

4、輸入活動時間voidsort(intalJ13J);〃排序voidoutput1(inta[][3]);〃排序的結(jié)果輸出intgreed(inta[][3],intarr[][ll][3],intm);//判斷記錄被選中的活動時間voidoutput2(inta[][ll][3],inty,intm);〃輸出最大的的活動時間intyi二0;intmain(){intan*ay[l1J[3J;intarr[ll][ll][3]={0J;intz,y,m,b[12J={0};input(array);sort(array);prmtf(,'n)

5、;output1(array);printf(““)；for(m=0;m<11;m++)b[m]=greed(array,an;m);y=0；for(m=0;m<11;m++)if(y

6、1);for(j=l；j<3;j++)scanf(”％d”,&a[i][j]);voidsort(inta[][3J){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+l][2]){t=aU][k];aU][k]=aU+l][k];aU+l][k]=t;voidoutput1(inta[]⑶){inti,j;printf("按結(jié)束時間的升序排列如下:");for(i=0;i

7、時間:H,a[i][0]);for(j=l；j<3;j++)printfC%da[i][j]);printf(un);intgreed(inta[][3],intarr[][ll][3],intm){inti,j,k,y=l;k=a[m][2];//for(i=0;iv3;i++)arr[yi]rO][i]=a[m][i];//for(i=m;i

8、put2(inta[][l1][3],inty,intm){inti,j；for(i=0;i