Python程序：求解完成所有工作的最短时间

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

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

  • 工人1：2 + 5 + 3 = 10

  • 工人2：1 + 8 = 9

所以最大时间是10。

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

  • 按降序排列jobs列表

  • assign := 前k个工作的列表

  • jobs := 剩余工作的列表

  • 定义一个函数dp()。它将接收i和assign作为参数。

  • 如果i等于jobs的大小，则

    • 返回assign中的最大值

  • ans := 无穷大

  • 对于x从0到k-1，执行：

    • 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))

输入

[2,1,3,8,5], 2

输出

10

更新于：2021年10月7日

757 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告