做6个页面的网站,江西省南昌市建筑工程网,上海房产网二手房出售,服装网站建设课程转自#xff1a;https://blog.csdn.net/bqw18744018044/article/details/80285414
总结#xff1a; 首先#xff0c;证明贪心的时候交换论证是万能的#xff01;其次#xff0c;这一点如果要满足#xff0c;也就是#xff0c;如果你要用交换论证法#xff0c;那么首先… 转自https://blog.csdn.net/bqw18744018044/article/details/80285414
总结 首先证明贪心的时候交换论证是万能的其次这一点如果要满足也就是如果你要用交换论证法那么首先要保证交换逆序后对其他的没有影响如果有影响那就只能像【POJ - 3253】Fence Repair 这道题一样用优先队列去解决了。 1. 单区间调度问题 问题定义存在单一资源有一组以时间区间形式表示的资源请求reqs{req-1, req-2, …, req-n}第i个请求希望占用资源一段时间来完成某些任务这段时间开始于begin(i)终止于end(i)。如果两个请求req-i和req-j在时间区间上没有重叠则说这两个请求是相容的求出这组请求的最大相容子集(最优子集)。举个例子有一间多媒体课室某一个周末有多个社团想要申请这间课室去举办社团活动每个社团都有一个对应的申请时间段比如周六上午8:00-10:00。求出这间课室在这个周末最多能满足几个社团的需求。
解决方案贪心算法优先选择最早结束的需求确保资源尽可能早地被释放把留下来满足其他需求的时间最大化。具体伪代码如下所示算法结束后集合A中会保留所有相容请求A的大小即是最大相容数量。
初始化R是所有需求的集合A为空集 对R中的需求Ri根据结束时间从早到晚排序 for Ri in R, do if Ri与A中的请求相容 A A并Ri endIf endFor return A 上述伪代码的C实现如下
#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 请求数量过多 endl; return 0; } for (int i 0; i requestNum; i) { cin req[i].begin req[i].end; } sort(req, req requestNum); vectorRequest 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. 多区间调度问题 问题定义存在多个(或者无限多个)相同的资源有一组以时间区间形式表示的资源请求reqs{req-1, req-2, …, req-n}第i个请求希望占用资源一段时间来完成某些任务这段时间开始于begin(i)终止于end(i)。如果两个请求req-i和req-j在时间区间上没有重叠则说这两个请求是相容的用尽可能少的资源满足所有请求(求最优资源数量)。举个例子有很多间课室某个周末有多个社团需要申请课室办活动每个社团都有一个对应的申请时间求最少需要多少间课室才能够满足所有社团的需求(在这个问题之中时间重叠的社团需要安排在其他课室即会使用到多个资源需要考虑多个资源上的调度安排故称为多区间调度)。
解决方案贪心算法将需求按照开始时间的早晚进行排序然后开始为这些资源打标签每个标签代表都一个资源需求req-i被打上标签k表示该请求分配到的资源是k。遍历排序后的需求如果一个需求与某个已分配资源上的其他安排不冲突则把该需求也放进该资源的安排考虑中如果冲突那么应该要给此需求分配新的资源已用资源数量加一。具体操作的伪代码如下所示。
对n个需求按照开始时间从早到晚进行排序 假设排序后的需求记为{R1, R2, ..., Rn} 初始化tagSize 1; for i1 to n, do: tags {1,2,...,tagSize}; for j 1 to i-1, do: if Rj与Ri时间区间重叠产生冲突: tags tags - {Rj的标签}; endIf endFor if tags为空集: tagSize 1; 将标签tagSize贴在Ri上 EndIf else: 在tags剩下的标签中随便挑一个贴给Ri endElse endFor 此时每个请求上都贴有标签每个标签对应其申请的资源编号此时的tagSize就是至少需要的资源数量 return tagSize; 上述伪代码的C实现如下
#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 请求数量过多 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. 最小延迟调度问题 问题定义存在单一资源和一组资源请求reqs{req-1, req-2, …, req-n}与前面两个问题不同这里的资源从时刻0开始有效(开始接受申请开始可以被使用)每个请求req-i都有一个截止时间ddl(i)每个请求都要占用资源一段连续的时间来完成任务占用时间为time(i)。每个请求都希望自己能在ddl之前完成任务不同需求必须被分在不重叠的时间区间(单一资源同一时刻只能满足一个请求)。假设我们计划满足每个请求但是允许某些请求延迟(即某个请求在ddl之后完成延误工期)确定一种合理的安排使得所有请求的延期时间中的最大值是所有可能的时间安排情况中最小的。从时刻0开始为每个请求req-i分配一个长度time(i)的时间区间把区间标记为[begin(i), end(i)]其中end(i) begin(i) time(i)。如果end(i) ddl(i)则请求req-i被延迟延迟时间为delay(i) end(i) - ddl(i)否则delay(i) 0。合理安排需求使得maxDelay max{delay(1), delay(2), …, delay(n)}是所有可能的安排中最小的。
解决方案贪心算法按照截止时间ddl排序越早截止的任务越早完成。该算法是一个没有空闲的最优调度即从时刻0开始都有在处理请求直到最后一个请求执行完释放资源之后才空闲。伪代码如下所示。
将需求按照截止时间进行排序 假设排序后的截止时间为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 则每个任务安排的时间区间为[begin[i], end[i]]所有任务中最大的延迟为maxDelaymaxDelay为所有可能的任务安排中最小的延迟 return maxDelay; 上述代码的C实现如下
#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 请求数量过多 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; }
转自https://blog.csdn.net/hongchh/article/details/52183614
代码格式不做调整详情请去原博主博客中看。
