最佳调度问题 题解

时间:2024-02-25 16:30:09

【题目描述】

假设有 n 个任务由 k 个可并行工作的机器来完成。完成任务 i 需要的 时间为 ti。试设计一个算法找到出完成这个 n 个任务的最佳调度,使得完成全部任务的时间最早。对任意给定的整数 n 和 k,以及完成任务 i 需要的时间为 ti,1<=i<=n。编程计算完成这 n 个任务的最佳调度。n<=20,k<=8

【输入】

第 1 行有 2 个正整数 n 和 k。第 2 行的 n 个正整数是完成 n 根任务需要的时间。

【输出】

计算出的完成全部任务的最早时间

【样例输入】

7 3

2 14 4 16 6 5 3

【样例输出】

17

==================题解==================

Dfs。

读入后先按降序排列,为机器开一个数组表示每个机器的工作时间,dfs函数中首先传入两个参数,分别是当前遍历到哪一个元素了与当前时间的最大值。之后对于当前元素枚举每个机器,找到放下此元素后不超过当前时间的最大值的机器,将时间加上之后调函数递归,传入的第二个参数就应该是此机器累加后的时间与原来最大时间的较大值,函数返回后要将所加上的时间再减掉。当达到最后一个元素时判断一下ans是否要更新,之后返回。