贪心算法之多机调度问题
2022/2/7 1:15:12
本文主要是介绍贪心算法之多机调度问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题:
某工厂有 n 个独立的作业,由 m 台相同的机器进行加工处理。作业 i 所需的加工时间为 ti ,任何作业在被处理时不能中 断,也不能进行拆分处理。现厂长请你给他写一个程序:算出 n 个作业由 m 台机器加工处理的最短时间 输入 第一行 T ( 1<T<100) 表示有 T 组测试数据。每组测试数据的第一行分别是整数 n , m ( 1<=n<=10000 , 1<=m<=100 ),接下来的一行是 n 个整数 ti ( 1<=t<=100) 。 输出 所需的最短时间贪心策略:每次选取剩余作业中执行时间最长的,分给最先结束作业的机器。 代码:
import java.util.Arrays; import java.util.Scanner; public class test { public static int getMatTime(int[] taskTime,int m){ int n=taskTime.length; //排序:递增 Arrays.sort(taskTime); int[] machines=new int[m]; if(n<=m){ return taskTime[n-1]; }else{ for (int i = n-1; i >=0 ; i--) { //找一个最先结束的机器,分配新的任务 int finsh=0; int machineTime=machines[finsh]; for (int j = 1; j < m; j++) { if(machines[j]<machineTime){ finsh=j; machineTime=machines[j]; } } //新的任务分配给最先结束的机器 machines[finsh]+=taskTime[i]; } } return findMat(machines); } private static int findMat(int[] machines) { int ret=machines[0]; for (int i = 0; i <machines.length ; i++) { ret=Math.max(ret,machines[i]); } return ret; } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int n,m; System.out.println("请输入任务个数和机器个数:"); n=scanner.nextInt(); m=scanner.nextInt(); System.out.println("输入任务的时间:"); int[] taskTime=new int[n] ; for (int i = 0; i <n ; i++) { taskTime[i]=scanner.nextInt(); } System.out.println("最短时间:"+getMatTime(taskTime,m)); } }
运行结果:
这篇关于贪心算法之多机调度问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求