資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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 次瀏覽
廣告