用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 。 输出格式: 第一行给出最优解的效益值。 第二行按照时间片分配顺序输出最优解J中的作业,中间用空格隔开,最后一个作业后面不要加空格。
时间: 2024-03-05 07:49:44 浏览: 110
用C语言解决各种排序问题
以下是带有期限的作业排序的C语言代码实现,使用了集合树方法:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int d; // 截止期限
int p; // 效益
} Job;
int cmp(const void *a, const void *b) {
return ((Job *)b)->p - ((Job *)a)->p; // 按效益从大到小排序
}
int main() {
int n, i, j, max_d = 0, max_p = 0;
scanf("%d", &n);
Job *jobs = (Job *)malloc(n * sizeof(Job)); // 存储作业的数组
for (i = 0; i < n; i++) {
scanf("%d %d", &jobs[i].d, &jobs[i].p);
if (jobs[i].d > max_d) max_d = jobs[i].d; // 找到最大的截止期限
if (jobs[i].p > max_p) max_p = jobs[i].p; // 找到最大的效益
}
qsort(jobs, n, sizeof(Job), cmp); // 按效益从大到小排序
int *set = (int *)calloc(max_d, sizeof(int)); // 集合树,用于判断作业的截止期限是否冲突
int sum_p = 0, num_jobs = 0; // sum_p表示最大效益值,num_jobs表示最优解J中作业的个数
for (i = 0; i < n; i++) {
for (j = jobs[i].d-1; j >= 0; j--) { // 从后往前查找集合树,找到空闲的时间插入作业
if (!set[j]) {
set[j] = jobs[i].p; // 将作业插入集合树
sum_p += jobs[i].p; // 更新最大效益值
num_jobs++; // 更新最优解J中作业的个数
break;
}
}
}
printf("%d\n", sum_p); // 输出最大效益值
for (i = 0; i < max_d; i++) {
if (set[i]) printf("%d ", set[i]); // 输出最优解J中的作业
}
printf("\n");
free(jobs);
free(set);
return 0;
}
```
该代码先将作业按效益从大到小排序,然后使用集合树方法插入作业,直到所有作业都插入完成。最后输出最大效益值和最优解J中的作业。
阅读全文