สมมติว่าเรามีอาร์เรย์ที่เรียกว่างาน โดยที่ jobs[i] ระบุระยะเวลาที่จำเป็นในการทำงาน ith ให้เสร็จสิ้น นอกจากนี้เรายังมีค่า k อีกค่าหนึ่งสำหรับพวกเขา เราสามารถกำหนดงานได้ ควรมอบหมายงานแต่ละงานให้กับผู้ปฏิบัติงานเพียงคนเดียว และเวลาทำงานของผู้ปฏิบัติงานคือเวลาทั้งหมดที่ใช้ในการทำงานทั้งหมดที่ได้รับมอบหมายให้เสร็จสมบูรณ์ เราต้องหาเวลาทำงานสูงสุดขั้นต่ำที่เป็นไปได้ของการมอบหมายงานใดๆ
ดังนั้น หากอินพุตเป็นเหมือนงาน =[2,1,3,8,5], k =2 ผลลัพธ์จะเป็น 10 เพราะเราสามารถกำหนดงานได้เช่น:
-
ผู้ปฏิบัติงาน1:2 + 5 + 3 =10
-
ผู้ปฏิบัติงาน 2:1 + 8 =9
เวลาสูงสุดคือ 10
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เรียงลำดับรายการงานในลำดับย้อนกลับ
-
assign :=รายการ k งานแรก
-
งาน :=รายการงานที่เหลืออยู่
-
กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i กำหนด
-
ถ้าฉันเท่ากับขนาดของงาน แล้ว
-
ผลตอบแทนสูงสุดที่ได้รับมอบหมาย
-
-
ตอบ :=อนันต์
-
สำหรับ x ในช่วง 0 ถึง k - 1 ทำ
-
assign :=รายการใหม่จากการมอบหมาย
-
assign[x] :=assign[x] + งาน[i]
-
ans :=ขั้นต่ำของ ans และ dp(i+1, กำหนด)
-
assign[x] :=assign[x] - งาน[i]
-
-
กลับมาอีกครั้ง
-
จากวิธีหลักส่งคืน dp(0, กำหนด)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
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
