貪心算法 活動安排問題

這道題的貪心算法比較容易理解，我就不多說明了，只是提到壹下算法思路1、建立數學模型描述問題。我在這裏將時間理解成壹條直線，上面有若幹個點，可能是某些活動的起始時間點，或終止時間點。在具體壹下，如果編程來實現的話，將時間抽象成鏈表數組，數組下標代表其實時間，該下標對應的鏈表代表在這個時間起始的活動都有哪些，具體參照程序註釋。2、問題分解。為了安排更多的活動，那麽每次選取占用時間最少的活動就好。那麽從壹開始就選取結束時間最早的，然後尋找在這個時間點上起始的活動，以此類推就可以找出貪心解。程序代碼：#include<stdio.h>

struct inode //自定義的結構體

{

int end; //表示結束時間

inode *next; //指向下壹個節點的指針

};int main()

{

inode start[10001],*pt;

int a,b,i,num=0; //num負責計數，i控制循環，a，b輸入時候使用

for(i=0;i<10001;i++) //初始化

{

start[i].next=NULL;

}

while(scanf("%d %d",&a,&b)) //輸入並建立數據結構

{

if(a==0&&b==0) break;

pt=new inode; //創建新的節點，然後將該節點插入相應的位置

pt->end=b;

pt->next=start[a].next;

start[a].next=pt;

}

i=0;

while(i<10001) //進行貪心算法，i表示當前時間

{

if(start[i].next==NULL)

{

i++; //該時間無活動開始

}

else

{

int temp=10001; //臨時變量，存儲該鏈表中最早的終止時間

for(pt=start[i].next;pt!=NULL;pt=pt->next)

{

if(pt->end<temp)

{

temp=pt->end;

}

}

i=temp; //將當前時間設置成前壹子問題的終止時間

num++;

}

}

printf("%d\n",num); //打印結果

return 0;

}代碼並不壹定是最快速的，但是可以求出貪心解，如果妳做的是ACM編程題目，不保證能AC註釋我盡力寫了，希望對妳有幫助。

上一篇:學金融工程的出來以後具體幹什麽工作？求專業人士指導

下一篇:軟件開發和軟件測試哪個更好