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

Posted on by

問題描述

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

貪心策略

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

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

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

這裡我選取第三種方法

算法設計

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

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

代碼實現

#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} };

按結束時間排序

冒泡排序實現即可：

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的開始時間加到第一個內容哦即可，隨後將第一個會議的結束時間設置為allowedTime，產生下一個不與第一個會議時間沖突的會議；然後自己加點輸出語句，美觀的運行出來結果就好瞭。

結束語

這算是貪心法第一個案例，也是比較好理解的一個案例，希望大傢分析後都能有自己的收獲，下篇博客再見，覺得好就鼓勵鼓勵博主吧

到此這篇關於C++超詳細講解貪心策略的設計及解決會場安排問題的文章就介紹到這瞭,更多相關C++貪心策略內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：