快捷導(dǎo)航

C++超詳細(xì)講解貪心策略的設(shè)計(jì)及解決會(huì)場安排問題

更新時(shí)間：2022年05月27日 10:44:16 作者：對(duì)象new不出來

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

問題描述

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

貪心策略

1、選擇最早開始時(shí)間且不與已安排會(huì)議重疊的會(huì)議

2、選擇使用時(shí)間最短且不與已安排會(huì)議重疊的會(huì)議

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

這里我選取第三種方法

算法設(shè)計(jì)

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

11個(gè)會(huì)議按結(jié)束時(shí)間的非減序排列表：

代碼實(shí)現(xiàn)

#include <iostream>
#include "會(huì)場安排.h"
#define n 11
struct meeting{
	int B;//開始時(shí)間
	int E;//結(jié)束時(shí)間
};
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<<"個(gè)會(huì)議號(hào)是 " << i+1 <<" 此會(huì)議開始時(shí)間為：" << M[i].B 
				<<" 此會(huì)議結(jié)束時(shí)間是：" << M[i].E << endl;
			allowedTime = M[i].E;
		}
	}
}

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

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

隨機(jī)輸入會(huì)議

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

按結(jié)束時(shí)間排序

冒泡排序?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;

}

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

最終會(huì)議確定

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

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