C++超詳細講解貪心策略的設計及解決會場安排問題

更新時間：2022年05月27日 10:44:16 作者：對象new不出來

為了更好的應對《算法設計與分析》這門課程，我把書上以及老師講過的案例都詳細的做一個重現(xiàn)及解剖，讓你熟記每一個潛在的考點，希望能給大家?guī)椭?/div>

問題描述

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

貪心策略

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

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

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

這里我選取第三種方法

算法設計

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

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

代碼實現(xiàn)

#include <iostream>
#include "會場安排.h"
#define n 11
struct meeting{
	int B;//開始時間
	int E;//結束時間
};
using namespace std;
int main()
{
	meeting M[n] = { {8,11}, {8,12}, {2,13}, {12,14}, {1,4},
		           {3,5}, {0,6}, {5,7}, {3,8}, {5,9}, {6,10} };
	for(int i=0;i<n;i++)
		for(int j=0;j<n-i-1;j++)
			if (M[j].E > M[j + 1].E) {
				meeting T;
				T = M[j]; M[j]= M[j+ 1]; M[j+1]= T;
			}
	int allowedTime = 0;
	for (int i = 0,j=0; i < n; i++) {
		if (M[i].B > allowedTime) {
			j++;
			cout << "安排的第"<<j<<"個會議號是 " << i+1 <<" 此會議開始時間為：" << M[i].B 
				<<" 此會議結束時間是：" << M[i].E << endl;
			allowedTime = M[i].E;
		}
	}
}

選擇結構體

定義meeting結構體，只設置會議開始時間B和結束時間E即可。

隨機輸入會議

n 為11

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

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

按結束時間排序

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

for(int i=0;i<n;i++)

for(int j=0;j<n-i-1;j++) if (M[j].E > M[j + 1].E)

{

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

}

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

最終會議確定

int allowedTime = 0;
for (int i = 0,j=0; i < n; i++) {
if (M[i].B > allowedTime) {
j++;
cout << "安排的第"<<j<<"個會議號是 " << i+1 <<" 此會議開始時間為：" << M[i].B
<<" 此會議結束時間是：" << M[i].E << endl;
allowedTime = M[i].E;
}
}

先將會議開始時間設置為0，只要把按結束時間升序排列的第一個大于0的開始時間加到第一個內(nèi)容哦即可，隨后將第一個會議的結束時間設置為allowedTime，產(chǎn)生下一個不與第一個會議時間沖突的會議；然后自己加點輸出語句，美觀的運行出來結果就好了。