LC 1723. 完成所有工作的最短时间
题目描述
这是 LeetCode 上的 1723. 完成所有工作的最短时间 ，难度为 困难。
给你一个整数数组 jobs ，其中 $jobs[i]$ 是完成第 $i$ 项工作要花费的时间。
请你将这些工作分配给 $k$ 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。
工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。
请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能「最小」的 最大工作时间 。
示例 1：1
2
3
4
5输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。
示例 2：1
2
3
4
5
6
7
8输入：jobs = [1,2,4,7,8], k = 2
输出：11
解释：按下述方式分配工作：
1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
2 号工人：4、7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。
提示：
- $1 <= k <= jobs.length <= 12$
- $1 <= jobs[i] <= 10^7$
DFS（TLE）
一看数据范围只有 $12$，我猜不少同学上来就想 DFS，但是注意 n 和 k 同等规模的，爆搜（DFS）的复杂度是 $O(k^n)$ 的。
那么极限数据下的计算量为 $12^{12}$，远超运算量 $10^7$。
抱着侥幸的心理一运行，很顺利的卡在了 $43/60$ 个数据：
1 | |
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class Solution {
int[] jobs;
int n, k;
int ans = 0x3f3f3f3f;
public int minimumTimeRequired(int[] _jobs, int _k) {
jobs = _jobs;
n = jobs.length;
k = _k;
int[] sum = new int[k];
dfs(0, sum, 0);
return ans;
}
/**
* u : 当前处理到那个 job
* sum : 工人的分配情况 例如：sum[0] = x 代表 0 号工人工作量为 x
* max : 当前的「最大工作时间」
*/
void dfs(int u, int[] sum, int max) {
if (max >= ans) return;
if (u == n) {
ans = max;
return;
}
for (int i = 0; i < k; i++) {
sum[i] += jobs[u];
dfs(u + 1, sum, Math.max(sum[i], max));
sum[i] -= jobs[u];
}
}
}
- 时间复杂度：$O(k^n)$
- 空间复杂度：$O(k)$
优先分配「空闲工人」的 DFS
那么 DFS 就没法过了吗？
除了 max >= ans 以外，我们还要做些别的剪枝吗？
我们可以重新审视一下这道题。
题目其实是让我们将 $n$ 个数分为 $k$ 份，并且尽可能让 $k$ 份平均。这样的「最大工作时间」才是最小的。
但在朴素的 DFS 中，我们是将每个任务依次分给每个工人，并递归此过程。
对应的递归树其实是一颗高度为 $n$ 的 $k$ 阶树。
所以其实我们第一次更新的 ans 其实是「最差」的答案（所有的任务都会分配给 $0$ 号工人），最差的 ans 为所有的 job 的总和（带编号的方块代表工人）:
因此我们朴素版的 DFS 其实是弱化了 max >= ans 剪枝效果的。
那么想要最大化剪枝效果，并且尽量让 $k$ 份平均的话，我们应当调整我们对于「递归树」的搜索方向：将任务优先分配给「空闲工人」（带编号的方块代表工人）：
树还是那棵树，但是搜索调整分配优先级后，我们可以在首次取得一个「较好」的答案，来增强我们的 max >= ans 剪枝效益。
事实上，当做完这个调整，我们能实现从 TLE 到 99% 的提升 🤣 🤣
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39class Solution {
int[] jobs;
int n, k;
int ans = 0x3f3f3f3f;
public int minimumTimeRequired(int[] _jobs, int _k) {
jobs = _jobs;
n = jobs.length;
k = _k;
int[] sum = new int[k];
dfs(0, 0, sum, 0);
return ans;
}
/**
* 【补充说明】不理解可以看看下面的「我猜你问」的 Q5 哦 ~
*
* u : 当前处理到那个 job
* used : 当前分配给了多少个工人了
* sum : 工人的分配情况 例如：sum[0] = x 代表 0 号工人工作量为 x
* max : 当前的「最大工作时间」
*/
void dfs(int u, int used, int[] sum, int max) {
if (max >= ans) return;
if (u == n) {
ans = max;
return;
}
// 优先分配给「空闲工人」
if (used < k) {
sum[used] = jobs[u];
dfs(u + 1, used + 1, sum, Math.max(sum[used], max));
sum[used] = 0;
}
for (int i = 0; i < used; i++) {
sum[i] += jobs[u];
dfs(u + 1, used, sum, Math.max(sum[i], max));
sum[i] -= jobs[u];
}
}
}
- 时间复杂度：$O(k^n)$
- 空间复杂度：$O(k)$
模拟退火
事实上，这道题还能使用「模拟退火」进行求解。
因为将 $n$ 个数划分为 $k$ 份，等效于用 $n$ 个数构造出一个「特定排列」，然后对「特定排列」进行固定模式的任务分配逻辑，就能实现「答案」与「最优排列」的对应关系。
基于此，我们可以使用「模拟退火」进行求解。
单次迭代的基本流程：
- 随机选择两个下标，计算「交换下标元素前对应序列的得分」&「交换下标元素后对应序列的得分」
- 如果温度下降（交换后的序列更优），进入下一次迭代
- 如果温度上升（交换前的序列更优），以「一定的概率」恢复现场（再交换回来）
对于一个能够运用模拟退火求解的问题，最核心的是如何实现
calc方法（即如何定义一个具体方案的得分），其余均为模板内容。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61class Solution {
int[] jobs;
int[] works = new int[20];
int n, k;
int ans = 0x3f3f3f3f;
Random random = new Random(20210508);
// 最高温/最低温/变化速率（以什么速度进行退火，系数越低退火越快，迭代次数越少，落入「局部最优」（WA）的概率越高；系数越高 TLE 风险越大）
double hi = 1e8, lo = 1e-4, fa = 0.90;
// 迭代次数，与变化速率同理
int N = 400;
// 计算当前 jobs 序列对应的最小「最大工作时间」是多少
int calc() {
Arrays.fill(works, 0);
for (int i = 0; i < n; i++) {
// [固定模式分配逻辑] : 每次都找最小的 worker 去分配
int idx = 0, cur = works[idx];
for (int j = 0; j < k; j++) {
if (works[j] < cur) {
cur = works[j];
idx = j;
}
}
works[idx] += jobs[i];
}
int cur = 0;
for (int i = 0; i < k; i++) cur = Math.max(cur, works[i]);
ans = Math.min(ans, cur);
return cur;
}
void shuffle(int[] nums) {
for (int i = n; i > 0; i--) {
int idx = random.nextInt(i);
swap(nums, idx, i - 1);
}
}
void swap(int[] arr, int i, int j) {
int c = arr[i];
arr[i] = arr[j];
arr[j] = c;
}
void sa() {
shuffle(jobs);
for (double t = hi; t > lo; t *= fa) {
int a = random.nextInt(n), b = random.nextInt(n);
int prev = calc(); // 退火前
swap(jobs, a, b);
int cur = calc(); // 退火后
int diff = cur - prev;
// 退火为负收益（温度上升），以一定概率回退现场
if (Math.log(diff / t) > random.nextDouble()) swap(jobs, a, b);
}
}
public int minimumTimeRequired(int[] _jobs, int _k) {
jobs = _jobs;
n = jobs.length;
k = _k;
while (N-- > 0) sa();
return ans;
}
}
- 时间复杂度：启发式搜索不讨论时空复杂度
- 空间复杂度：启发式搜索不讨论时空复杂度
我猜你问
Q0. 模拟退火有何风险？
随机算法，会面临 WA 和 TLE 风险。
Q1. 模拟退火中的参数如何敲定的？
根据经验猜的，然后提交。根据结果是 WA 还是 TLE 来决定之后的调参方向。如果是 WA 说明部分数据落到了「局部最优」或者尚未达到「全局最优」。
Q2. 参数如何调整？
如果是 WA 了，一般我是优先调大 fa 参数，使降温变慢，来变相增加迭代次数；如果是 TLE 了，一般是优先调小 fa 参数，使降温变快，减小迭代次数。总迭代参数 N 也是同理。
可以简单理解调大 fa 代表将「大步」改为「baby step」，防止越过全局最优，同时增加总执行步数。
可以结合我不同的 fa 参数的提交结果来感受下：
Q3. 关于「模拟退火」正确性？
随机种子不变，测试数据不变，迭代参数不变，那么退火的过程就是恒定的，必然都能找到这些测试样例的「全局最优」。
Q4. 需要掌握「模拟退火」吗？
还是那句话，特别特别特别有兴趣的可以去了解一下。
但绝对是在你已经彻底理解「剪枝 DFS」和我没写的「状态压缩 DP」之后再去了解。
Q5. 在「剪枝 DFS」中为什么「优先分配空闲工人」的做法是对的？
首先要明确，递归树还是那棵递归树。
所谓的「优先分配空闲工人」它并不是「贪心模拟」思路，而只是一个「调整搜索顺序」的做法。
「优先分配空闲工人」不代表不会将任务分配给有工作的工人，仅仅代表我们先去搜索那些「优先分配空闲工人」的方案。
然后将得到的「合法解」配合 max >= ans 去剪枝掉那些「必然不是最优解」的方案。
本质上，我们并没有主动的否决某些方案（也就是我们并没有改动递归树），我们只是调整了搜索顺序来剪枝掉了一些「必然不是最优」的搜索路径。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1723 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
