貪心算法解活動安排實驗報告

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

1、實驗3貪心算法解活動安排問題一、實驗要求1．要求按貪心法求解問題；2．要求讀文本文件輸入活動安排時間區(qū)間數(shù)據(jù)；3．要求顯示結(jié)果。二、實驗儀器和軟件平臺儀器：帶usb接口微機(jī)軟件平臺：WIN-XP+VC++6.0三、源程序#include"stdafx.h"#include#include#include#defineN50#defineTURE1#defineFALSE0ints[N];/*開始時間*/intf[N];/*結(jié)束時間*/intA[N];/*用A存儲所有的*/intPartition(in

2、t*b,int*a,intp,intr);voidQuickSort(int*b,int*a,intp,intr);voidGreedySelector(intn,int*s,int*f,int*A);intmain(){intn=0,i;while(n<=0

3、

4、n>50){printf("");printf("請輸入活動的個數(shù),n=");scanf("%d",&n);if(n<=0)printf("請輸入大于零的數(shù)!");elseif(n>50)printf("請輸入小于50的數(shù)!");}printf("請分別輸入開始時間s[i]和結(jié)束時間f[i]:

5、");for(i=1;i<=n;i++){printf("s[%d]=",i,i);scanf("%d",&s[i]);printf("f[%d]=",i,i);scanf("%d",&f[i]);printf("");}QuickSort(s,f,1,n);//按結(jié)束時間非減序排列printf("按結(jié)束時間非減序排列如下:");/*輸出排序結(jié)果*/printf("序號t開始時間結(jié)束時間");printf("-------------------------");for(i=1;i<=n;i++)printf("%dt%dt%

6、d",i,s[i],f[i]);printf("-------------------------");GreedySelector(n,s,f,A);//貪心算法實現(xiàn)活動安排printf("安排的活動序號依次為：");for(i=1;i<=n;i++){if(A[i])printf("%d%d-->%d",i,s[i],f[i]);}printf("");system("pause");return0;}//快速排序voidQuickSort(int*b,int*a,intp,intr){intq;if(p

7、a,p,r);QuickSort(b,a,p,q-1);/*對左半段排序*/QuickSort(b,a,q+1,r);/*對右半段排序*/}}//產(chǎn)生中間數(shù)intPartition(int*b,int*a,intp,intr){intk,m,y,i=p,j=r+1;intx=a[p];y=b[p];while(1){while(a[++i]x);if(i>=j)break;else{k=a[i];a[i]=a[j];a[j]=k;m=b[i];b[i]=b[j];b[j]=m;}}a[p]=a[j];b[p]=b[j];a[j

8、]=x;b[j]=y;returnj;}//貪心算法實現(xiàn)活動安排voidGreedySelector(intn,int*s,int*f,int*A){//用集合A來存儲所選擇的活動A[1]=TURE;//默認(rèn)從第一次活動開始執(zhí)行intj=1;//j記錄最近一次加入到A中的活動for(inti=2;i<=n;i++){//f[j]為當(dāng)前集合A中所有活動的最大結(jié)束時間//活動i的開始時間不早于最近加入到集合A中的j的時間f[j]if(s[i]>=f[j]){A[i]=TURE;//當(dāng)A[i]=TURE時，活動i在集合A中j=i;}elseA[i]=FALSE;}}

9、四、運(yùn)行結(jié)果五、實驗小結(jié)貪心算法總是做出在當(dāng)前看來最好的選擇，也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇?；顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。