第C++超詳細講解貪心策略的設(shè)計及解決會場安排問題目錄問題描述貪心策略算法設(shè)計代碼實現(xiàn)選擇結(jié)構(gòu)體隨機輸入會議按結(jié)束時間排序最終會議確定結(jié)束語

問題描述

設(shè)有n個會議的集合C={1,2,,n}，其中每個會議都要求使用同一個資源（如會議室），而在同一時間內(nèi)只能有一個會議使用該資源。每個會議i都有要求使用該資源的起始時間bi和結(jié)束時間ei，且biei。如果選擇了會議i使用會議室，則它在半開區(qū)間[bi,ei)內(nèi)占用該資源。如果[bi,ei)與[bj,ej)不相交，則稱會議i與會議j是相容的。會場安排問題要求在所給的會議集合中選出最大的相容活動子集，也即盡可能地選擇更多的會議來使用資源。

貪心策略

1、選擇最早開始時間且不與已安排會議重疊的會議

2、選擇使用時間最短且不與已安排會議重疊的會議

3、選擇具有最早結(jié)束時間且不與已安排會議重疊的會議

這里我選取第三種方法

算法設(shè)計

設(shè)有11個會議等待安排，用貪心法找出滿足目標(biāo)要求的會議集合。這些會議按結(jié)束時間的非減序排列如表所示

11個會議按結(jié)束時間的非減序排列表：

代碼實現(xiàn)

#includeiostream

#include"會場安排.h"

#definen11

structmeeting{

intB;//開始時間

intE;//結(jié)束時間

usingnamespacestd;

intmain()

meetingM[n]={{8,11},{8,12},{2,13},{12,14},{1,4},

{3,5},{0,6},{5,7},{3,8},{5,9},{6,10}};

for(inti=0;ii++)

for(intj=0;jn-i-1;j++)

if(M[j].EM[j+1].E){

meetingT;

T=M[j];M[j]=M[j+1];M[j+1]=T;

intallowedTime=0;

for(inti=0,j=0;ii++){

if(M[i].BallowedTime){

j++;

cout"安排的第"j"個會議號是"i+1"此會議開始時間為："M[i].B

"此會議結(jié)束時間是："M[i].Eendl;

allowedTime=M[i].E;

}

選擇結(jié)構(gòu)體

定義meeting結(jié)構(gòu)體，只設(shè)置會議開始時間B和結(jié)束時間E即可。

隨機輸入會議

n為11

meetingM[n]={{8,11},{8,12},{2,13},{12,14},{1,4},

{3,5},{0,6},{5,7},{3,8},{5,9},{6,10}};

按結(jié)束時間排序

冒泡排序?qū)崿F(xiàn)即可：

for(inti=0;ii++)

for(intj=0;jn-i-1;j++)if(M[j].EM[j+1].E)

{

meetingT;T=M[j];M[j]=M[j+1];M[j+1]=T;

}

這里的中間變量必須設(shè)置為meeting類型，以便于將會議的所有屬性都交換

最終會議確定

intallowedTime=0;

for(inti=0,j=0;ii++){

if(M[i].BallowedTime){

j++;

cout安排的第j個會議號是i+1此會議開始時間為：M[i].B

此會議結(jié)束時間是：M[i].Eendl;

allowedTime=M[i].E;

}

}

先將會議開始時間設(shè)置為0，只要把按結(jié)束時間升序排列的第一個大于0的開始時間加到第一個內(nèi)容哦即可，隨后將第一個會議的結(jié)束時間設(shè)置為allowedTime，產(chǎn)生下一個不與第一個會議時間沖突的會議；然后自己加點