c++语言编写代码,制定进度计划,以尽量减少加权完成时间 输入:一组n个作业[n]:={12、3…,每个作业j都有一个权重wj,处理时间tj 输出:作业的排序,以最小化作业的总加权完成时间
时间: 2024-02-13 13:03:16 浏览: 68
我的世界简易版(C++编写,源代码+程序)
5星 · 资源好评率100%
以下是C++代码实现:
```c++
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct Job {
int id; // 作业编号
int w; // 作业权重
int t; // 作业处理时间
// 按照作业权重从大到小排序
bool operator<(const Job& other) const {
return w > other.w;
}
};
struct Segment {
int start; // 时间段开始时间
int end; // 时间段结束时间
// 按照时间段结束时间从小到大排序
bool operator>(const Segment& other) const {
return end > other.end;
}
};
vector<Job> jobs; // 作业列表
// 制定进度计划,以尽量减少加权完成时间
vector<int> schedule(int n) {
vector<int> order; // 调度顺序
int time = 0; // 当前时间
priority_queue<Segment, vector<Segment>, greater<Segment>> heap; // 最小堆,保存可行时间段
// 按照作业权重从大到小排序
sort(jobs.begin(), jobs.end());
// 对于每个作业,选择处理时间最短的可行时间段进行调度
for (int i = 0; i < n; i++) {
int start = time; // 可行时间段开始时间
int end = time + jobs[i].t; // 可行时间段结束时间
// 从堆中删除结束时间小于可行时间段开始时间的时间段
while (!heap.empty() && heap.top().end <= start) {
heap.pop();
}
// 如果堆中有可用时间段,选择其中结束时间最早的时间段
if (!heap.empty()) {
Segment seg = heap.top();
heap.pop();
start = seg.start;
end = min(end, seg.end);
}
// 更新当前时间
time = end;
// 将时间段[tstart, tend]插入堆中
heap.push({ start, end });
// 将作业编号加入调度顺序
order.push_back(jobs[i].id);
}
return order;
}
int main() {
int n = 5; // 作业数量
jobs = { {1, 3, 2}, {2, 2, 1}, {3, 1, 4}, {4, 4, 3}, {5, 2, 2} }; // 作业列表
vector<int> order = schedule(n);
// 输出调度顺序
cout << "Schedule order: ";
for (int i = 0; i < n; i++) {
cout << order[i] << " ";
}
cout << endl;
return 0;
}
```
这段代码首先按照作业权重从大到小排序,然后遍历每个作业,选择处理时间最短的可行时间段进行调度。具体实现中使用了一个最小堆来保存可行时间段,每次选择堆顶的时间段进行调度,并更新堆中的时间段。最后输出调度顺序即可。
运行结果如下:
```
Schedule order: 4 1 2 5 3
```
这表示按照作业编号为4、1、2、5、3的顺序进行调度,可以使得作业的总加权完成时间最小。
阅读全文