? ? ? ? ?會場用來安排活動，每個活動有一個開始時間和一個結(jié)束時間，在某個活動的開始時間到結(jié)束時間這段范圍內(nèi)，其他活動不能再被安排，求最多能安排多少場活動。

#include<stdio.h> #include<stdlib.h>void GreedySelector(int n,int s[],int f[],int A[]){int i,j;A[1]=1;//第一個活動要選，第一個結(jié)束時間最短,A[i]=1表示第i個活動入選j=1;//j=1表示取第一個活動的結(jié)束時間for(i=2;i<=n;i++){ //用i遍歷每個活動if(s[i]>f[j]){ //這個活動的開始時間小于上個活動的結(jié)束時間A[i]=1;j=i;}else{A[i]=0;}} }int main(){int i;//每個活動按活動的結(jié)束時間進(jìn)行排序int s[] = {0,1,3,0,5,3,5,6 ,8 ,8 ,2,12};//活動的開始時間int f[] = {0,4,5,6,7,8,9,10,11,12,13,14};//活動的結(jié)束時間int n=11,A[11];GreedySelector(n,s,f,A);for(i=1;i<=n;i++){if(A[i] == 1){printf("%d\n",i);}}return 0; }

運行結(jié)果:1? ?4? 8? 11? ? ? 這4個下標(biāo)對應(yīng)的活動

策略選擇：1.開始時間最早優(yōu)先（證明不可行）? ?2.占用時間少優(yōu)先(證明不可行)? 3.結(jié)束時間最早優(yōu)先(使用貪心算法可以得到最優(yōu)解)

?

學(xué)習(xí)地址：https://www.bilibili.com/video/BV1yT4y1u7Ju?from=search&seid=7410797215453072339

總結(jié)

以上是生活随笔為你收集整理的贪心算法--会场安排问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。