Chương trình tìm thời gian tối thiểu hoàn thành tất cả công việc trong Python

Mô tả bài toán

Cho mảng jobs (thời gian mỗi việc) và k người làm. Mỗi việc giao cho đúng 1 người. Thời gian làm của người = tổng thời gian việc được giao. Tìm giá trị nhỏ nhất có thể của thời gian làm lớn nhất.

Ví dụ

jobs = [2,1,3,8,5], k = 2 -> 10 (Người 1: 2+5+3=10, Người 2: 1+8=9).

Giải thuật (Backtracking + Pruning)

1. Sắp xếp jobs giảm dần.
2. Gán k việc đầu cho k người.
3. Đệ quy dp(i, assign): gán việc i cho từng người, cập nhật assign, gọi đệ quy i+1.
4. Cắt tỉa: nếu max(assign) >= ans hiện tại thì dừng nhánh đó.

Triển khai Python

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