用c语言贪心法写出下面题目并给出详细注释 带有期限的作业排序要解决的是操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题,形式化描述为: ①只能在一台机器上处理n个作业,每个作业i=1,...,n均可在单位时间内完成; ②每个作业i都有一个期限值d i >0,(d i 是整数); ③当且仅当作业i在它的截止期限前被完成时获得p i >0的效益; 问题的可行解是这n个作业的一个子集合J。J中的每个作业都能在各自的截止期限之前完成,产生一个作业效益之和∑p i 。具有最大效益值的可行解就是最优解。 要求用更快的作业排序算法(利用集合树方法)实现。 输入格式: 第一行为一个不超过200的正整数n,表示作业的个数; 接下来的n行,每行两个正整数(中间用空格隔开),表示每个作业i的截止期限d i 和按期完成产生的效益p i
时间: 2024-02-20 20:58:23 浏览: 69
一个更快的带有期限的作业排序问题,排序算法数据结构 最快的排序算法
以下是使用C语言贪心算法解决带有期限的作业排序问题的代码和注释:
```c
#include <stdio.h>
#include <stdlib.h>
// 作业结构体
typedef struct job {
int deadline; // 截止期限
int profit; // 收益
} Job;
// 按照截止期限从小到大排序
int cmp(const void* a, const void* b) {
return ((Job*)a)->deadline - ((Job*)b)->deadline;
}
int main() {
int n;
scanf("%d", &n);
// 创建作业数组
Job* jobs = (Job*)malloc(sizeof(Job) * n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &jobs[i].deadline, &jobs[i].profit);
}
// 按照截止期限从小到大排序
qsort(jobs, n, sizeof(Job), cmp);
// 记录每个时间点能够完成的最大收益
int* maxProfit = (int*)calloc(n, sizeof(int));
// 遍历每个作业
for (int i = 0; i < n; i++) {
int deadline = jobs[i].deadline;
int profit = jobs[i].profit;
// 从后往前搜索,找到第一个能够完成该作业的时间点
for (int j = deadline - 1; j >= 0; j--) {
if (maxProfit[j] == 0) {
maxProfit[j] = profit;
break;
}
}
}
int totalProfit = 0;
// 计算最大收益
for (int i = 0; i < n; i++) {
totalProfit += maxProfit[i];
}
printf("最大收益为:%d\n", totalProfit);
free(jobs);
free(maxProfit);
return 0;
}
```
注释已经在代码中给出,简单说明一下算法的思路:
1. 将所有作业按照截止期限从小到大排序。
2. 遍历每个作业,从后往前搜索,找到第一个能够完成该作业的时间点。
3. 记录每个时间点能够完成的最大收益。
4. 计算最大收益。
这个算法的时间复杂度为O(n^2),如果使用集合树方法,可以将时间复杂度优化到O(nlogn)。
阅读全文