โปรแกรมหาเวลาน้อยที่สุดเสร็จงานทั้งหมดใน Python

มีอาร์เรย์ jobs เวลาแต่ละงาน และ k คนงาน แบ่งงานให้แต่ละคน 1 งาน เวลาทำงานของคน = ผลรวมงานที่ได้รับ หา ค่าสูงสุดของเวลาทำงาน ที่น้อยที่สุด (makespan)

ตัวอย่าง: jobs=[2,1,3,8,5], k=2 ผลลัพธ์ 10 (คน1: 2+5+3=10, คน2: 1+8=9)

วิธีแก้ปัญหา (Backtracking + Pruning)

1. เรียง jobs ใหญ่ไปเล็ก
2. มอบ k งานแรกให้คนแต่ละคน
3. DFS มอบงานที่เหลือ ลองมอบให้แต่ละคน เก็บค่าต่ำสุด

ตัวอย่างโค้ด

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