带有期限的作业排序要解决的是操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题,形式化描述为: ①只能在一台机器上处理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中的作业,中间用空格隔开,最后一个作业后面不要加空格。C语言实现
时间: 2024-03-24 16:36:34 浏览: 10
以下是一个使用集合树方法实现带有期限的作业排序的 C 语言程序:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 200
// 定义作业结构体
struct Job {
int deadline; // 截止期限
int profit; // 效益
int index; // 作业编号
};
// 按照截止期限从小到大排序的比较函数
int cmp(const void* a, const void* b) {
struct Job* p = (struct Job*)a;
struct Job* q = (struct Job*)b;
return p->deadline - q->deadline;
}
// 计算最大效益和输出最优解
void schedule(struct Job jobs[], int n) {
int i, j, k, max_profit = 0;
int* parent = (int*)malloc((n + 1) * sizeof(int));
int* rank = (int*)malloc((n + 1) * sizeof(int));
int* ans = (int*)malloc(n * sizeof(int));
// 初始化并查集
for (i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 0;
}
// 遍历所有作业
for (i = 0; i < n; i++) {
// 找到该作业的根节点
j = jobs[i].deadline;
while (j > 0 && parent[j] != j) {
j = parent[j];
}
// 如果根节点大于0,则说明该作业可以完成
if (j > 0) {
max_profit += jobs[i].profit;
// 将该作业加入并查集
j = parent[j];
parent[j] = j - 1;
rank[j] = 1;
ans[jobs[i].index - 1] = 1;
}
// 否则,找到比该作业根节点更小的节点
else {
for (j = jobs[i].deadline - 1; j > 0; j--) {
if (rank[j] == 0) {
break;
}
}
// 如果找到了节点,则将该作业加入并查集
if (j > 0) {
max_profit += jobs[i].profit;
parent[j] = j - 1;
rank[j] = 1;
ans[jobs[i].index - 1] = 1;
}
}
}
// 输出最大效益值和最优解
printf("%d\n", max_profit);
for (i = 0; i < n; i++) {
if (ans[i]) {
printf("%d ", i + 1);
}
}
printf("\n");
free(parent);
free(rank);
free(ans);
}
int main() {
int n, i;
struct Job jobs[MAX_N];
// 读入作业数据
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d%d", &jobs[i].deadline, &jobs[i].profit);
jobs[i].index = i + 1;
}
// 按照截止期限从小到大排序
qsort(jobs, n, sizeof(struct Job), cmp);
// 调用作业排序算法
schedule(jobs, n);
return 0;
}
```
该程序先读入作业数据,然后按照截止期限从小到大排序。接着,使用集合树方法遍历所有作业,对于每个作业,如果其截止期限大于0,就将其加入并查集,并更新最大效益值和最优解;否则,就找到比该作业截止期限更小的节点,并将其加入并查集。最后,输出最大效益值和最优解。