貪心算法----活動時間安排.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);????}??