Giả sử chúng ta có một mảng được gọi là công việc, trong đó công việc [i] cho biết lượng thời gian cần thiết để hoàn thành công việc thứ i. Chúng ta cũng có một giá trị k khác, chúng ta có thể giao việc cho họ. Mỗi công việc nên được giao cho chính xác một công nhân. Và thời gian lao động của công nhân là tổng thời gian để hoàn thành mọi công việc được giao cho họ. Chúng tôi phải tìm ra thời gian làm việc tối đa tối thiểu có thể có của bất kỳ nhiệm vụ nào.
Vì vậy, nếu đầu vào giống như công việc =[2,1,3,8,5], k =2, thì đầu ra sẽ là 10 bởi vì, chúng ta có thể gán các công việc như:
-
Công nhân 1:2 + 5 + 3 =10
-
Công nhân 2:1 + 8 =9
Vì vậy, thời gian tối đa là 10.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
sắp xếp danh sách công việc theo thứ tự ngược lại
-
gán:=danh sách k công việc đầu tiên
-
việc làm:=danh sách các công việc còn lại
-
Định nghĩa một hàm dp (). Điều này sẽ đưa tôi, chỉ định
-
nếu tôi bằng quy mô công việc, thì
-
trả lại tối đa của chỉ định
-
-
ans:=infinity
-
đối với x trong phạm vi từ 0 đến k - 1, thực hiện
-
gán:=một danh sách mới từ gán
-
gán [x]:=gán [x] + công việc [i]
-
ans:=tối thiểu ans và dp (i + 1, gán)
-
giao [x]:=giao [x] - công việc [i]
-
-
trả lại ans
-
từ phương thức chính trả về dp (0, gán)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn
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)) Đầu vào
[2,1,3,8,5], 2
Đầu ra
10