## 题目地址(1723. 完成所有工作的最短时间)

https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/

## 题目描述

```
给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。

返回分配方案中尽可能 最小 的 最大工作时间 。

 

示例 1：

输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。


示例 2：

输入：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] <= 107
```

## 前置知识

- 位运算
- 回溯
- 剪枝
- 子集枚举

## 公司

- 暂无

## 方法一：二分 + 回溯 + 贪心 + 剪枝

### 思路

题目的解空间不难得出为 [max(jobs), sum(jobs)]。

因此可以使用能力检测二分来做。不熟悉能力检测二分的可以先看下我的[二分专题](https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-search-2.md)，接下来套用最左二分模板即可。

需要注意的是**能力检测** 部分，我们需要枚举所有的情况，而不是像大多数能力检测二分那样直接一次遍历，这是因为这道题可以**不连续** 地选择多个 job。这提示我们使用回溯来解决。

初始化一个长度为 k 的 workloads， workloads[i] 表示第 i 个工人👷目前的工时。如果第 i 个工人可以做，就**贪心地**进行选择。否则，我们尝试下一个 job。

除此之外，我们需要对算法进行剪枝，否则无法通过所有的测试用例。

- 剪枝 1：优先选择时间长的任务，这样在很多情况下可以有效减少递归的深度，尤其是短任务较多的情况。
- 剪枝 2：如果某一个任务太大，直接超过了 limit，我们可以提前退出，因此不可能存在一种可行解。

### 关键点

- 剪枝（否则会超时）

### 代码

- 语言支持：Python3

```py
class Solution:
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
        def backtrack(pos, workloads, limit):
            if pos >= len(jobs): return True
            for i in range(len(workloads)):
                workload = workloads[i]
                if jobs[pos] + workload <= limit:
                    workloads[i] += jobs[pos]
                    if backtrack(pos + 1, workloads, limit): return True
                    workloads[i] -= jobs[pos]
                # 剪枝
                if workload == 0:
                    return False
            return False
        def possible(limit):
            return backtrack(0, [0] * k, limit)
        # 剪枝
        jobs.sort(reverse=True)
        l, r = jobs[0], sum(jobs)
        while l <= r:
            mid = (l + r) // 2
            if possible(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l
```

## 方法二：状压 DP

### 思路

回溯和状压 DP 很多时候会一起出现。

这道题的数据范围提示我**可能使用状压 DP**，因此数据范围很小。通常这种情况，就是直接对数据范围很小的那个变量做状态压缩，**用 n 位的数字来表示选取情况**，并且一般 n 不会超过 20。

定义 dp[i][j] 表示使用 i 个 工人，完成任务情况如 j 所表示的最小的最大工作时间。

其中 j 就是一个 n 位的二进制数，其中 n 为 jobs 长度。数字上第
k 二进制位为 1 表示选取任务 k，否则表示不选取任务 k。

那么转移方程为：

<!-- $$
  dp[i][j]=\left\{
  \begin{aligned}
  min(dp[i][j], max(dp[i-1][j - sub], sum[sub])) &  & i > 0 \\
  sum[j] & & i == 0 \\
  \end{aligned}
  \right.
$$ -->

![](https://tva1.sinaimg.cn/large/008i3skNly1gs0a7pgkgaj30u204ejrs.jpg)

其中 sub 是 j 的子集， sum(sub) 指的是任务情况如 sub 二进制表示那样的完成的**总时间**。

因此我们必须枚举所有 j 的子集 sub。这里枚举子集可进行子集枚举优化策略，具体可看我的 91 天学算法的《基础篇 - 枚举》部分的讲义 。

提示：

这种子集枚举的题目，推荐使用 C++。如果使用 Python，则很可能会超时。

### 代码

- 语言支持：C++，Python3

C++ Code:

```c++

class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        int n = jobs.size();
        vector<int> sum(1 << n);
        for (int i = 0; i < (1 << n); i++) {
            for(int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    sum[i] += jobs[j];
                }
            }
        }

        vector<vector<int>> dp(k, vector<int>(1 << n));
        for (int i = 0; i < (1 << n); i++) {
            dp[0][i] = sum[i];
        }

        for (int i = 1; i < k; i++) {
           // 二进制子集枚举优化
            for (int j = 0; j < (1 << n); j++) {
                dp[i][j] = INT_MAX;
                for (int x = j; x; x = (x - 1) & j) {
                    dp[i][j] = min(dp[i][j], max(dp[i - 1][j - x], sum[x]));
                }
            }
        }
        return dp[k - 1][(1 << n) - 1];
    }
};


```

Python3 Code（超时）:

```py
class Solution:
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
        n = len(jobs)
        sum_jobs = [0] * (1 << n)
        dp = [[float("inf") for _ in range(1 << n)] for _ in range(k)]

        for i in range(1 << n):
            for j in range(n):
                if i & 1 << j:
                    sum_jobs[i] += jobs[j]

        for i in range(1 << n):
            dp[0][i] = sum_jobs[i]

        for i in range(1, k):
            #  二进制子集枚举优化
            for j in range(1 << n):
                sub = j
                while sub != 0:
                    dp[i][j] = min(dp[i][j], max(dp[i - 1][j - sub], sum_jobs[sub]))
                    sub = j & (sub - 1)
        return dp[-1][-1]

```

**复杂度分析**

令 n 为数组长度。

- 时间复杂度：$O(2^n)$
- 空间复杂度：$O(2^n)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
