题目描述
给定一个整数数组 jobs
,其中 jobs[i]
是完成第 i
项工作要花费的时间。
请你将这些工作分配给 k
位工人。所有工作都应该分配给工人,且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案,使工人的 最大工作时间 得以 最小化。
返回分配方案中尽可能 最小 的 最大工作时间。
样例
输入:jobs = [3,2,3], k = 3
输出:3
解释:给每位工人分配一项工作,最大工作时间是 3。
输入: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
算法1
(状态压缩动态规划,子集枚举) $O(n \cdot 2^n + k \cdot 3^n)$
- 设状态 $f(i, s)$ 表示 $i$ 个人完成状态为 $s$ 的任务时的最小的最大工作时间。其中,$i$ 的有效下标从 1 开始,$s$ 的范围是 $0$ 到 $2^n - 1$。
- 初始时,$f(0, 0) = 0$,其余为正无穷。
- 转移时,对于 $f(i, s)$,枚举 $s$ 的非空子集 $sub$,令第 $i$ 个人完成 $sub$,转移 $f(i, s) = \min(f(i, s), \max(f(i - 1, s - sub), sum[sub]))$。其中 $sum$ 可以预处理出来。
- 最终答案为 $f(k, 2^n - 1)$。
时间复杂度
- 预处理需要 $O(n \cdot 2^n)$ 的时间。
- 动态规划状态数为 $O(k \cdot 2^n)$,对于每个人,总的转移时间为 $O(3^n)$。
- 故总时间复杂度为 $O(n \cdot 2^n + k \cdot 3^n)$
空间复杂度
- 需要 $O(k \cdot 2^n)$ 的空间存储预处理数组和状态。
C++ 代码
class Solution {
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
const int n = jobs.size();
const int INF = 1000000000;
vector<vector<int>> f(k + 1, vector<int>(1 << n, INF));
vector<int> sum(1 << n, 0);
for (int s = 0; s < (1 << n); s++)
for (int i = 0; i < n; i++)
if (s & (1 << i))
sum[s] += jobs[i];
f[0][0] = 0;
for (int i = 1; i <= k; i++)
for (int s = 0; s < (1 << n); s++)
for (int sub = s; sub > 0; sub = (sub - 1) & s)
f[i][s] = min(f[i][s], max(f[i - 1][s ^ sub], sum[sub]));
return f[k][(1 << n) - 1];
}
};
算法2
(二分答案,状态压缩动态规划) $O(n \cdot 2^n \cdot \log S)$
- 求最大值最小,可以通过二分答案转判定性问题,二分的下界为所有工作的最大值,上界为工作的时间总和 $S$。
- 假设当前的限定值为 $lim$,求此时最少需要多少个人。
- 设状态 $f(s)$ 表示完成状态为 $s$ 时,所需要的最少人数,以及在这个人数下,最后一个人最少的占用时间。
- 初始时,$f(0) = (0, +\infty)$,其余为 $(+\infty, +\infty)$。
- 转移时,对于 $f(s)$,枚举某个工作 $i$,判断 $f(s - 2^i)$ 的状态如何转移到 $f(s)$,并更新 $f(s)$ 的最小值。
- 最终返回的值为 $f(2^n - 1).first$。
时间复杂度
- 二分的区间为 $S$。
- 每次动态规划的状态数为 $O(2^n)$,转移时间为 $O(n)$。
- 故总时间复杂度为 $O(n \cdot 2^n \cdot \log S)$。
- 其实可以进一步优化,由于待定的答案一定是 $2^n$ 种组合中的一个,所以时间复杂度可以优化为 $O(n \cdot 2^n \log 2^n) = O(n^2 \cdot 2^n)$。
空间复杂度
- 需要 $O(2^n)$ 的空间存储状态。
C++ 代码
#define INF 1000000000
class Solution {
private:
int calc(int lim, const vector<int> &jobs) {
const int n = jobs.size();
vector<pair<int, int>> f(1 << n, make_pair(INF, INF));
f[0].first = 0;
f[0].second = INF;
for (int s = 1; s < (1 << n); s++) {
for (int i = 0; i < n; i++) {
if (!(s & (1 << i)))
continue;
pair<int, int> t;
if (f[s ^ (1 << i)].second + jobs[i] > lim) {
t.first = f[s ^ (1 << i)].first + 1;
t.second = jobs[i];
} else {
t.first = f[s ^ (1 << i)].first;
t.second = f[s ^ (1 << i)].second + jobs[i];
}
f[s] = min(f[s], t);
}
}
return f[(1 << n) - 1].first;
}
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
int l = 0, r = 0;
for (int x : jobs) {
r += x;
l = max(l, x);
}
while (l < r) {
int mid = (l + r) >> 1;
if (calc(mid, jobs) <= k) r = mid;
else l = mid + 1;
}
return l;
}
};
还想问一下,为啥二分的解法中,都放在最后一个人上面,放在前面的不可以吗,谢谢
因为当前工作与上一个人的安排有关,如果排不下了,就得新开一个人
放在前边的情况也已经被考虑到了,因为是二进制组合的方式,前面的人也可以换到后边
还是不太明白,比方说某个人放到最后一个可能超过了limit,但是放到前面还是不满,所以在这种情况下没必要新开一个吧。但是按照老哥的解法,只判断了最后一个位置满不满
你说的这种情况可以和把前面不满的组看做最后一个
但是老哥代码是按顺序判断的吧,比如三个数,大小分别为2,7,3,limit是8,一个一个判断,第一个数放在第一组,第二个数放在第二组,按照老哥代码,第三个数放在第二组不够放了,就放在了第三组,但是其实第三个数可以放在第一组的。我是哪里思考有问题吗,谢谢
但实际上顺序可以是 7 3 2
第二个二分答案解释4写错了,初始时,f(0)=(0,+∞),其余为(0,+∞)。 应该是其余为(+∞,+∞)
已修正
你好,请问第一个方法的复杂度的$3^n$部分是咋来的,没看懂,我只看出来是$k2^n2^n$。
另外方法一空间应该可以降到$O(2^n)$
枚举子集的所有子集总的时间复杂度就是 $3^n$,可以自行想一下证明
空间可以通过滚动数组优化到 $2^n$
原来如此,学到了。
搜到了你的回答: https://www.acwing.com/community/content/513/
能解释下枚举 s 的非空子集 sub时
这句话什么意思吗?
这个是通过巧妙的位运算找到下一个恰好比当前小的子集