Python中计算所有工作完成所需的最短时间程序

假设我们有一个名为jobs的数组，其中jobs[i]表示完成第i个工作需要的时间。此外，我们还有另一个值k，可以分配给他们的工作。每个工作应分配给恰好一个工人。一个工人的工作时间是完成分配给他们的所有工作所需的总时间。我们必须找到任何分配的最小可能最大的工作时间。

因此，如果输入为jobs = [2,1,3,8,5]，k = 2，则输出将为10，因为我们可以将工作分配如下：

工人1：2 + 5 + 3 = 10
工人2：1 + 8 = 9

因此，最大时间是10。

要解决这个问题，我们将执行以下步骤 –

将jobs列表按相反的顺序排序
将前k个工作分配给assign列表
将remaining jobs分配给jobs列表
定义一个名为dp（）的函数。这将采取i，assign
如果i与jobs的大小相同，则
- 返回assign的最大值
ans = infinity
- for x in range 0 to k – 1, do
  - assign =从assign获取新列表
  - assign[x] = assign [x] + jobs[i]
  - ans = ans和dp（i + 1，assign）的最小值
  - assign[x] = assign [x] – jobs[i]
返回ans
从主方法中返回dp（0，assign）

示例

让我们看一下以下实现以获得更好的理解

def solve(jobs, k):
    jobs.sort(reverse=True)
    assign = tuple(jobs[:k])
    jobs = jobs[k:]

    def dp(i, assign):
        if i == len(jobs):
            return max(assign)

        ans = float('inf')
        for x in range(k):
            assign = list(assign)
            assign[x] += jobs[i]
            ans = min(ans, dp(i+1, tuple(assign)))
            assign[x] -= jobs[i]

        return ans

    return dp(0, assign)

jobs = [2,1,3,8,5]
k = 2
print(solve(jobs, k))