# 1723. 完成所有工作的最短时间

### 题目地址(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)]。

因此可以使用能力检测二分来做。不熟悉能力检测二分的可以先看下我的[二分专题](/leetcode-solution/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。

那么转移方程为：

![](https://p.ipic.vip/47u63j.jpg)

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

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

提示：

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

#### 代码

* 语言支持：C++，Python3

C++ Code:

```

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://p.ipic.vip/26rxxs.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1723.find-minimum-time-to-finish-all-jobs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.