调度以最小化加权完成时间 输入:一组n个作业[n]:={1,2,3,••, N),每个作业j的权重为wj,处理时间为t 输出:作业的排序,以最小化作业的,总加权完成时间。具体代码
时间: 2024-02-12 07:09:45 浏览: 173
以下是具体的代码实现,使用了C++语言:
```C++
#include <bits/stdc++.h>
using namespace std;
struct Job {
int id, w, t;
bool operator<(const Job& other) const {
return w * other.t > t * other.w;
}
};
vector<Job> jobs;
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int w, t;
cin >> w >> t;
jobs.push_back({i, w, t});
}
sort(jobs.begin(), jobs.end());
int sum_t = 0, ans = 0;
for (auto job : jobs) {
sum_t += job.t;
ans += job.w * sum_t;
}
cout << ans << endl;
return 0;
}
```
其中,结构体`Job`存储了作业的编号、权重和处理时间。在结构体中,我们定义了小于号运算符,用于对作业按照权重与处理时间的比值从大到小排序。
读入作业权重和处理时间后,我们使用`sort`函数对作业进行排序,然后依次计算每个作业的加权完成时间,最后得到的就是最小化的作业总加权完成时间。
该算法的时间复杂度为O(nlogn),其中n为作业的数量。
阅读全文