从直观感觉来说,我们应该尽可能将任务均分到若干个工人那里。
这就导致了,同样是递归回溯,不同的递归思路和决策优先级会有着不同的效率
v 1.0
这是我第一次写的递归回溯解法。
思路:在 dfs 中决策每一个人任务该分给哪个工人(有编号 0 ~ k - 1 的工人可以选择)
LC 超时。
class Solution {
int min = Integer.MAX_VALUE;
public int minimumTimeRequired(int[] jobs, int k) {
int n = jobs.length;
int[] sum = new int[k];
dfs(jobs, n, 0, k, sum, 0);
return min;
}
// n 代表任务总数u 代表当前决策到哪个任务;k 为工人总数;sum 对应了每个工人的工作量总和;max 记录了决策过程总的最大值
void dfs(int[] jobs, int n, int u, int k, int[] sum, int max) {
if (max >= min) return;
if (u == n) {
System.out.println(" ");
min = max;
return;
}
for (int i = 0; i < k; i++) {
sum[i] += jobs[u];
System.out.println(i + "个人 --- 选择第" + u + "件 --- 任务" + jobs[u]);
dfs(jobs, n, u + 1, k, sum, Math.max(max, sum[i]));
sum[i] -= jobs[u];
}
}
}
执行测试数据,可以发现递归树展开次数达到 537660 次,仍未求得解
[46,13,54,51,38,49,54,67,26,78,33]
10
部分打印:
2个人 — 选择第9件 — 任务78
3个人 — 选择第9件 — 任务78
4个人 — 选择第9件 — 任务78
5个人 — 选择第9件 — 任务78
6个人 — 选择第9件 — 任务78
7个人 — 选择第9件 — 任务78
8个人 — 选择第9件 — 任务78
9个人 — 选择第9件 — 任务78
1个人 — 选择第8件 — 任务26
0个人 — 选择第9件 — 任务78
1个人 — 选择第9件 — 任务78
0个人 — 选择第10件 — 任务33
1个人 — 选择第10件 — 任务33
2个人 — 选择第10件 — 任务33
3个人 — 选择第10件 — 任务33
4个人 — 选择第10件 — 任务33
5个人 — 选择第10件 — 任务33
6个人 — 选择第10件 — 任务33
7个人 — 选择第10件 — 任务33
8个人 — 选择第10件 — 任务33
9个人 — 选择第10件 — 任务33
2个人 — 选择第9件 — 任务78
3个人 — 选择第9件 — 任务78
4个人 — 选择第9件 — 任务78
…
… 537660 more lines
v 2.0
这是看了 y 总讲解之后写的递归回溯解法。
思路:还是在 dfs 中决策每个任务,但不是一上来就假定可以分给所以工人,而是分给正在工作的工人,再决策分给新的工人。
而且这种做法是优先派给已经在工作的工人,然后再决策给新的工人。
LC 2ms
class Solution {
int min = Integer.MAX_VALUE;
public int minimumTimeRequired(int[] jobs, int k) {
int n = jobs.length;
int[] sum = new int[k];
dfs(jobs, 0, 0, sum, 0);
return min;
}
// a 为当前决策的任务;b 为当前已经在工作的工人(0 代表没有工人工作过,1代表当前有一个工人工作过);sum 代表每个工人的工作量;max 记录决策过程中的最大值
void dfs(int[] jobs, int a, int b, int[] sum, int max) {
if (max >= min) return;
int n = jobs.length;
if (a == n) {
System.out.println(" ");
min = max;
return;
}
for (int i = 0; i < b; i++) {
sum[i] += jobs[a];
System.out.println(i + "个人 --- 选择第" + a + "件 --- 任务" + jobs[a]);
dfs(jobs, a + 1, b, sum, Math.max(max, sum[i]));
sum[i] -= jobs[a];
}
if (b < sum.length) {
sum[b] = jobs[a];
System.out.println(b + "个人 --- 选择第" + a + "件 --- 任务" + jobs[a]);
dfs(jobs, a + 1, b + 1, sum, Math.max(max, sum[b]));
sum[b] = 0;
}
}
}
执行测试数据,可以发现递归树展开次数达到 956 次,求得解
[46,13,54,51,38,49,54,67,26,78,33]
10
部分打印:
0个人 — 选择第0件 — 任务46
0个人 — 选择第1件 — 任务13
0个人 — 选择第2件 — 任务54
0个人 — 选择第3件 — 任务51
0个人 — 选择第4件 — 任务38
0个人 — 选择第5件 — 任务49
0个人 — 选择第6件 — 任务54
0个人 — 选择第7件 — 任务67
0个人 — 选择第8件 — 任务26
0个人 — 选择第9件 — 任务78
0个人 — 选择第10件 — 任务33
1个人 — 选择第10件 — 任务33
1个人 — 选择第9件 — 任务78
0个人 — 选择第10件 — 任务33
1个人 — 选择第10件 — 任务33
2个人 — 选择第10件 — 任务33
…
… 956 more lines
v 3.0
递归回溯任务第三版。
思路:和上面的第二版是一样的,但是是优先决策给新的工人,再决策给已经在工作的工人
LC 0ms
class Solution {
int min = Integer.MAX_VALUE;
public int minimumTimeRequired(int[] jobs, int k) {
int n = jobs.length;
int[] sum = new int[k];
dfs(jobs, 0, 0, sum, 0);
return min;
}
void dfs(int[] jobs, int a, int b, int[] sum, int max) {
if (max >= min) return;
int n = jobs.length;
if (a == n) {
System.out.println(" ");
min = max;
return;
}
if (b < sum.length) {
sum[b] = jobs[a];
System.out.println(b + "个人 --- 选择第" + a + "件 --- 任务" + jobs[a]);
dfs(jobs, a + 1, b + 1, sum, Math.max(max, sum[b]));
sum[b] = 0;
}
for (int i = 0; i < b; i++) {
sum[i] += jobs[a];
System.out.println(i + "个人 --- 选择第" + a + "件 --- 任务" + jobs[a]);
dfs(jobs, a + 1, b, sum, Math.max(max, sum[i]));
sum[i] -= jobs[a];
}
}
}
执行测试数据,可以发现递归树展开次数达到 395 次,求得解
[46,13,54,51,38,49,54,67,26,78,33]
10
部分打印:
1个人 — 选择第1件 — 任务13
2个人 — 选择第2件 — 任务54
3个人 — 选择第3件 — 任务51
4个人 — 选择第4件 — 任务38
5个人 — 选择第5件 — 任务49
6个人 — 选择第6件 — 任务54
7个人 — 选择第7件 — 任务67
8个人 — 选择第8件 — 任务26
9个人 — 选择第9件 — 任务78
0个人 — 选择第10件 — 任务33
1个人 — 选择第10件 — 任务33
2个人 — 选择第10件 — 任务33
3个人 — 选择第10件 — 任务33
4个人 — 选择第10件 — 任务33
5个人 — 选择第10件 — 任务33
6个人 — 选择第10件 — 任务33
7个人 — 选择第10件 — 任务33
…
… 395 more lines
求一个主定理分析时间复杂度
T(n) = aT(n/b)+O(n^d)