轉(zhuǎn)自：https://blog.csdn.net/bqw18744018044/article/details/80285414

總結(jié)：

? 首先，證明貪心的時(shí)候交換論證是萬能的！其次，這一點(diǎn)如果要滿足，也就是，如果你要用交換論證法，那么首先要保證交換逆序后，對(duì)其他的沒有影響！如果有影響，那就只能像【POJ - 3253】Fence Repair?這道題一樣，用優(yōu)先隊(duì)列去解決了。

---

1. 單區(qū)間調(diào)度問題
問題定義：存在單一資源，有一組以時(shí)間區(qū)間形式表示的資源請(qǐng)求reqs={req-1, req-2, …, req-n}，第i個(gè)請(qǐng)求希望占用資源一段時(shí)間來完成某些任務(wù)，這段時(shí)間開始于begin(i)終止于end(i)。如果兩個(gè)請(qǐng)求req-i和req-j在時(shí)間區(qū)間上沒有重疊，則說這兩個(gè)請(qǐng)求是相容的，求出這組請(qǐng)求的最大相容子集(最優(yōu)子集)。舉個(gè)例子：有一間多媒體課室，某一個(gè)周末有多個(gè)社團(tuán)想要申請(qǐng)這間課室去舉辦社團(tuán)活動(dòng)，每個(gè)社團(tuán)都有一個(gè)對(duì)應(yīng)的申請(qǐng)時(shí)間段，比如周六上午8:00-10:00。求出這間課室在這個(gè)周末最多能滿足幾個(gè)社團(tuán)的需求。

解決方案：貪心算法，優(yōu)先選擇最早結(jié)束的需求，確保資源盡可能早地被釋放，把留下來滿足其他需求的時(shí)間最大化。具體偽代碼如下所示，算法結(jié)束后集合A中會(huì)保留所有相容請(qǐng)求，A的大小即是最大相容數(shù)量。

初始化R是所有需求的集合，A為空集
對(duì)R中的需求Ri，根據(jù)結(jié)束時(shí)間從早到晚排序
for Ri in R, do
? if Ri與A中的請(qǐng)求相容
? ? A = A并Ri
? endIf
endFor
return A

上述偽代碼的C++實(shí)現(xiàn)如下，

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_SIZE = 100;

struct Request {
? int begin, end;
} req[MAX_SIZE];

bool operator<(const Request& req1, const Request& req2) {
? return req1.end < req2.end;
}

int main() {
? int requestNum;
? cin >> requestNum;
? if (requestNum > MAX_SIZE) {
? ? cout << "請(qǐng)求數(shù)量過多" << endl;
? ? return 0;
? }
? for (int i = 0; i < requestNum; ++i) {
? ? cin >> req[i].begin >> req[i].end;
? }

? sort(req, req + requestNum);

? vector<Request> rvec;
? rvec.push_back(req[0]);
? for (int i = 1; i < requestNum; ++i) {
? ? if (rvec[rvec.size() - 1].end <= req[i].begin) {
? ? ? rvec.push_back(req[i]);
? ? }
? }

? cout << "最大兼容量: " << rvec.size() << endl;
? return 0;
}

2. 多區(qū)間調(diào)度問題
問題定義：存在多個(gè)(或者無限多個(gè))相同的資源，有一組以時(shí)間區(qū)間形式表示的資源請(qǐng)求reqs={req-1, req-2, …, req-n}，第i個(gè)請(qǐng)求希望占用資源一段時(shí)間來完成某些任務(wù)，這段時(shí)間開始于begin(i)終止于end(i)。如果兩個(gè)請(qǐng)求req-i和req-j在時(shí)間區(qū)間上沒有重疊，則說這兩個(gè)請(qǐng)求是相容的，用盡可能少的資源滿足所有請(qǐng)求(求最優(yōu)資源數(shù)量)。舉個(gè)例子：有很多間課室，某個(gè)周末有多個(gè)社團(tuán)需要申請(qǐng)課室辦活動(dòng)，每個(gè)社團(tuán)都有一個(gè)對(duì)應(yīng)的申請(qǐng)時(shí)間，求最少需要多少間課室才能夠滿足所有社團(tuán)的需求(在這個(gè)問題之中時(shí)間重疊的社團(tuán)需要安排在其他課室，即會(huì)使用到多個(gè)資源，需要考慮多個(gè)資源上的調(diào)度安排，故稱為多區(qū)間調(diào)度)。

解決方案：貪心算法，將需求按照開始時(shí)間的早晚進(jìn)行排序，然后開始為這些資源打標(biāo)簽，每個(gè)標(biāo)簽代表都一個(gè)資源，需求req-i被打上標(biāo)簽k表示該請(qǐng)求分配到的資源是k。遍歷排序后的需求，如果一個(gè)需求與某個(gè)已分配資源上的其他安排不沖突，則把該需求也放進(jìn)該資源的安排考慮中；如果沖突，那么應(yīng)該要給此需求分配新的資源，已用資源數(shù)量加一。具體操作的偽代碼如下所示。

對(duì)n個(gè)需求按照開始時(shí)間從早到晚進(jìn)行排序
假設(shè)排序后的需求記為{R1, R2, ..., Rn}
初始化tagSize = 1;
for i=1 to n, do:
? tags = {1,2,...,tagSize};
? for j = 1 to i-1, do:
? ? if Rj與Ri時(shí)間區(qū)間重疊產(chǎn)生沖突:
? ? ? tags = tags - {Rj的標(biāo)簽};
? ? endIf
? endFor
? if tags為空集:
? ? tagSize += 1;
? ? 將標(biāo)簽tagSize貼在Ri上
? EndIf
? else:
? ? 在tags剩下的標(biāo)簽中隨便挑一個(gè)貼給Ri
? endElse
endFor
此時(shí)每個(gè)請(qǐng)求上都貼有標(biāo)簽，每個(gè)標(biāo)簽對(duì)應(yīng)其申請(qǐng)的資源編號(hào)，此時(shí)的tagSize就是至少需要的資源數(shù)量
return tagSize;


上述偽代碼的C++實(shí)現(xiàn)如下：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_SIZE = 100;

struct Request {
? int begin, end, tag;
} req[MAX_SIZE];

bool operator<(const Request& req1, const Request& req2) {
? return req1.begin < req2.begin;
}

int main() {
? int requestNum;
? cin >> requestNum;
? if (requestNum > MAX_SIZE) {
? ? cout << "請(qǐng)求數(shù)量過多" << endl;
? ? return 0;
? }
? for (int i = 0; i < requestNum; ++i) {
? ? cin >> req[i].begin >> req[i].end;
? }

? sort(req, req + requestNum);

? int tagSize = 1;
? req[0].tag = 0;
? bool tags[MAX_SIZE];
? for (int i = 1; i < requestNum; ++i) {
? ? memset(tags, 1, sizeof(tags));
? ? for (int j = 0; j < i; ++j) {
? ? ? if (req[j].end > req[i].begin) {
? ? ? ? tags[req[j].tag] = false;
? ? ? }
? ? }
? ? bool isTagsEmpty = true;
? ? int tag;
? ? for (int j = 0; j < tagSize; ++j) {
? ? ? if (tags[j]) {
? ? ? ? isTagsEmpty = false;
? ? ? ? tag = j;
? ? ? ? break;
? ? ? }
? ? }
? ? if (isTagsEmpty) {
? ? ? req[i].tag = tagSize;
? ? ? ++tagSize;
? ? } else {
? ? ? req[i].tag = tag;
? ? }
? }

? cout << "最小資源使用量: " << tagSize << endl;
? return 0;
}


3. 最小延遲調(diào)度問題
問題定義：存在單一資源和一組資源請(qǐng)求reqs={req-1, req-2, …, req-n}，與前面兩個(gè)問題不同，這里的資源從時(shí)刻0開始有效(開始接受申請(qǐng)，開始可以被使用)，每個(gè)請(qǐng)求req-i都有一個(gè)截止時(shí)間ddl(i)，每個(gè)請(qǐng)求都要占用資源一段連續(xù)的時(shí)間來完成任務(wù)，占用時(shí)間為time(i)。每個(gè)請(qǐng)求都希望自己能在ddl之前完成任務(wù)，不同需求必須被分在不重疊的時(shí)間區(qū)間(單一資源，同一時(shí)刻只能滿足一個(gè)請(qǐng)求)。假設(shè)我們計(jì)劃滿足每個(gè)請(qǐng)求，但是允許某些請(qǐng)求延遲(即某個(gè)請(qǐng)求在ddl之后完成，延誤工期)，確定一種合理的安排，使得所有請(qǐng)求的延期時(shí)間中的最大值，是所有可能的時(shí)間安排情況中最小的。從時(shí)刻0開始，為每個(gè)請(qǐng)求req-i分配一個(gè)長(zhǎng)度time(i)的時(shí)間區(qū)間，把區(qū)間標(biāo)記為[begin(i), end(i)]，其中end(i) = begin(i) + time(i)。如果end(i) > ddl(i)，則請(qǐng)求req-i被延遲，延遲時(shí)間為delay(i) = end(i) - ddl(i)；否則delay(i) = 0。合理安排需求，使得maxDelay = max{delay(1), delay(2), …, delay(n)}是所有可能的安排中最小的。

解決方案：貪心算法，按照截止時(shí)間ddl排序，越早截止的任務(wù)越早完成。該算法是一個(gè)沒有空閑的最優(yōu)調(diào)度，即從時(shí)刻0開始都有在處理請(qǐng)求，直到最后一個(gè)請(qǐng)求執(zhí)行完釋放資源之后才空閑。偽代碼如下所示。

將需求按照截止時(shí)間進(jìn)行排序
假設(shè)排序后的截止時(shí)間為ddl[1]<=...<=ddl[n]
start = 0;
maxDelay = 0;
for i = 1 to n, do:
? begin[i] = start;
? end[i] = start + time[i];
? start = end[i] + time[i];
? if maxDelay < end[i] - ddl[i]:
? ? L = end[i] - ddl[i];
? endIf
endFor
則每個(gè)任務(wù)安排的時(shí)間區(qū)間為[begin[i], end[i]]，所有任務(wù)中最大的延遲為maxDelay，maxDelay為所有可能的任務(wù)安排中最小的延遲
return maxDelay;

上述代碼的C++實(shí)現(xiàn)如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_SIZE = 100;

struct Request {
? int time, ddl;
? int begin, end;
} req[MAX_SIZE];

bool operator<(const Request& req1, const Request& req2) {
? return req1.ddl < req2.ddl;
}

int main() {
? int requestNum;
? cin >> requestNum;
? if (requestNum > MAX_SIZE) {
? ? cout << "請(qǐng)求數(shù)量過多" << endl;
? ? return 0;
? }
? for (int i = 0; i < requestNum; ++i) {
? ? cin >> req[i].time >> req[i].ddl;
? }

? sort(req, req + requestNum);

? int start = 0, maxDelay = 0;
? for (int i = 0; i < requestNum; ++i) {
? ? req[i].begin = start;
? ? req[i].end = start + req[i].time;
? ? start += req[i].time;
? ? if (maxDelay < req[i].end - req[i].ddl) {
? ? ? maxDelay = req[i].end - req[i].ddl;
? ? }
? }

? cout << "最小的最大延遲: " << maxDelay << endl;
? return 0;
}

轉(zhuǎn)自：https://blog.csdn.net/hongchh/article/details/52183614

代碼格式不做調(diào)整，詳情請(qǐng)去原博主博客中看。

總結(jié)

以上是生活随笔為你收集整理的贪心算法 -- 最小延迟调度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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