用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 13:49:44 浏览: 20
以下是带有期限的作业排序的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中的作业。

相关推荐

最新推荐

recommend-type

用C语言实现从文本文件中读取数据后进行排序的功能

是一个十分可靠的程序,这个程序的查错能力非常强悍。程序包含了文件操作,归并排序和字符串输入等多种技术。对大家学习C语言很有帮助,有需要的一起来看看。
recommend-type

C语言实现车辆出租管理系统

主要为大家详细介绍了C语言实现车辆出租管理系统,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
recommend-type

C语言实现简单航班管理系统

主要为大家详细介绍了C语言实现简单航班管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
recommend-type

餐馆点菜系统C语言源代码

主要为大家详细介绍了餐馆点菜系统C语言源代码,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
recommend-type

C语言实现食堂就餐管理系统(带链表)

主要为大家详细介绍了C语言实现食堂就餐管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

【实战演练】MATLAB用遗传算法改进粒子群GA-PSO算法

![MATLAB智能算法合集](https://static.fuxi.netease.com/fuxi-official/web/20221101/83f465753fd49c41536a5640367d4340.jpg) # 2.1 遗传算法的原理和实现 遗传算法(GA)是一种受生物进化过程启发的优化算法。它通过模拟自然选择和遗传机制来搜索最优解。 **2.1.1 遗传算法的编码和解码** 编码是将问题空间中的解表示为二进制字符串或其他数据结构的过程。解码是将编码的解转换为问题空间中的实际解的过程。常见的编码方法包括二进制编码、实数编码和树形编码。 **2.1.2 遗传算法的交叉和
recommend-type

openstack的20种接口有哪些

以下是OpenStack的20种API接口: 1. Identity (Keystone) API 2. Compute (Nova) API 3. Networking (Neutron) API 4. Block Storage (Cinder) API 5. Object Storage (Swift) API 6. Image (Glance) API 7. Telemetry (Ceilometer) API 8. Orchestration (Heat) API 9. Database (Trove) API 10. Bare Metal (Ironic) API 11. DNS
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。