用 Python 编写程序，找出完成所有工作所需的最短时间

pythonserver side programmingprogramming更新于 2025/12/9 14:04:17

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

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

Worker1:2 + 5 + 3 = 10
Worker2:1 + 8 = 9

因此最大时间为 10。

为了解决这个问题，我们将遵循以下步骤 −

按相反顺序对任务列表进行排序
assign := 前 k 个任务列表
jobs := 剩余任务列表
定义一个函数 dp() 。这将获取 i，分配
如果 i 与作业大小相同，则
- 返回分配的最大值
ans := infinity
对于范围为 0 到 k - 1 的 x，执行
- 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))