用C语言实现,假设有n(n<=20)个任务由k(k<=20)个可并行工作的机器完成。完成任务i需要的时间为ti。 试设计一个算法,对任意给定的整数n和k,以及完成任务i 需要的时间为ti ,i=1~n。计算完成这n个任务的最佳调度,使得完成全部任务的时间最早。 输入格式: 输入数据的第一行有2 个正整数n和k。第2 行的n个正整数是完成n个任务需要的时间。 输出格式: 将计算出的完成全部任务的最早时间输出到屏幕。 输入样例: 在这里给出一组输入。例如: 7 3 2 14 4 16 6 5 3 输出样例: 在这里给出相应的输出。例如: 17
时间: 2023-06-17 22:04:02 浏览: 100
最佳调度问题,假设有n个任务由k个可并行工作的机器完成
5星 · 资源好评率100%
这是一道经典的任务调度问题,可以使用贪心算法进行求解。具体做法是,将任务按照完成时间从大到小排序,然后依次将任务分配给当前完成时间最早的机器。具体实现步骤如下:
1. 读入 n 和 k 以及每个任务的完成时间 t[i]。
2. 对任务按照完成时间从大到小排序。
3. 初始化每个机器的完成时间为 0。
4. 依次将任务分配给当前完成时间最早的机器,即将任务分配给完成时间最早的机器,更新该机器的完成时间。
5. 输出所有机器中完成时间最晚的时间,即为最优调度时间。
C语言代码实现如下:
阅读全文