用C++实现下列代码 输入:作业的数量n,n个作业的编号ij,权值wj,处理所需要的时间tj 输出:最小化作业的总加权完成时间以及该情况下作业的处理顺序
时间: 2024-02-13 18:02:26 浏览: 15
这是一个经典的作业调度问题。可以使用贪心算法来解决。
首先,根据每个作业的权值和处理时间计算它的单位时间权值(ui = wi / ti)。然后按照单位时间权值从大到小对所有作业进行排序。
接下来,依次处理每个作业。对于当前正在处理的作业,累加它的处理时间,计算它的加权完成时间。将当前作业加入到处理顺序中。
最后输出作业的总加权完成时间和处理顺序即可。
下面是C++代码实现:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Job {
int id;
int weight;
int time;
double unitWeight;
};
bool cmp(const Job& a, const Job& b) {
return a.unitWeight > b.unitWeight;
}
int main() {
int n;
cin >> n;
vector<Job> jobs(n);
for (int i = 0; i < n; i++) {
jobs[i].id = i + 1;
cin >> jobs[i].weight >> jobs[i].time;
jobs[i].unitWeight = (double)jobs[i].weight / jobs[i].time;
}
sort(jobs.begin(), jobs.end(), cmp);
int totalTime = 0;
double totalWeightedTime = 0;
vector<int> order;
for (int i = 0; i < n; i++) {
totalTime += jobs[i].time;
totalWeightedTime += jobs[i].weight * totalTime;
order.push_back(jobs[i].id);
}
cout << "Minimum total weighted time: " << totalWeightedTime << endl;
cout << "Job processing order: ";
for (int i = 0; i < n; i++) {
cout << order[i] << " ";
}
cout << endl;
return 0;
}
```
输入示例:
```
5
3 4
1 2
5 3
4 1
2 5
```
输出示例:
```
Minimum total weighted time: 60.8
Job processing order: 3 1 2 4 5
```