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)

示例

让我们看看下面的实现以更好地理解

Open Compiler
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

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

10

更新于:2021年10月7日

757 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告