C++实现使用贪心法解决机器作业问题

问题描述：
有 $n$ 个作业需要在一台机器上执行，一个时刻机器上只能执行一个作业，每个作业可在单位时间内完成，作业 $i$ 有截止时间 $d_i$ ，当作业 $i$ 在截止时间被执行完，则可获得 $p_i$ 的收益。求最大收益。

思路：
我们选择用贪心算法来求解。
先将所有作业按照收益从大到小排序，然后按顺序遍历所有作业，把 最靠近每个作业的截止时间的空闲时间 分配给该作业，若无空闲时间则跳过该作业。

源代码：

//
//
main.cpp
//
MachineOperation
//
//
Created by 胡昱 on 2021/12/31.
//
#include <iostream>
#include <algorithm>
using namespace std;
// 作业结构体
struct Operation{
int ddl;
// 截止时间
int w;
// 收益
};
// 根据收益比较作业
int compareByW(const void* a, const void* b) {
return -(int)(((Operation*)a)->w - ((Operation*)b)->w);
}
int main(int argc, const char * argv[]) {
// 共T组测试数据
int T;
cin >> T;
while((T--) > 0) {
// 输入作业数量
int N;
cin >> N;
// 创建并输入作业数组N
Operation* ops = new Operation[N];
int maxDDL = 0;
// 记录最大截止时间
for(int ni = 0; ni < N; ++ni) {
Operation op;
cin >> op.ddl >> op.w;
ops[ni] = op;
if(op.ddl > maxDDL) {
maxDDL = op.ddl;
}
}
// 最大截止时间等于0的话说明没有活动可以被选择
if(maxDDL == 0) {
cout << 0 << endl;
continue;
}
// 创建时间数组来记录每个时间是否被占用，并初始化
int* busyTime = new int[maxDDL + 1];
for(int ti = 0; ti <= maxDDL; ++ti) {
busyTime[ti] = 0;
}
// 因为是贪心算法，所以我们按收益大小进行排序
qsort(ops, N, sizeof(Operation), compareByW);
// 初始化结果
int result = 0;
// 开始选择作业
for(int opi = 0; opi < N; ++opi) {
// 是否有空闲时间执行该作业
bool hasFreeTime = false;
// 从DDL开始往前寻找空闲时间
int time = ops[opi].ddl;
while(time > 0) {
if(busyTime[time] == 0) {
hasFreeTime = true;
break;
}
else {
--time;
}
}
// 判断是否执行该作业
if(hasFreeTime) {
// 设置改时间已被占用
busyTime[time] = 1;
// 增加收益
result += ops[opi].w;
}
}
// 输出结果并释放资源
cout << result << endl;
delete [] ops;
delete [] busyTime;
}
return 0;
}

最后

以上就是老迟到牛排为你收集整理的C++实现使用贪心法解决机器作业问题的全部内容，希望文章能够帮你解决C++实现使用贪心法解决机器作业问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。