Chương trình kiểm tra có thể thực thi tất cả task với core server cho trước Python

Cho danh sách cores (số core của từng server) và tasks (số core cần cho từng task). Mỗi task chỉ chạy trên một server, một server có thể chạy nhiều task. Kiểm tra có phân bổ được tất cả task không.

Ví dụ: cores=[10,7], tasks=[7,3,2,2,1] → True (server 10 chạy task 7+3, server 7 chạy 2+2+1).

Giải thuật (Backtracking)

1. Nếu tasks rỗng → True
2. Thử gán task đầu tiên vào từng server có đủ core
3. Đệ quy kiểm tra phần task còn lại
4. Backtrack: hoàn tác gán nếu không thành công

Ví dụ triển khai

def solve(cores, tasks):
    if not tasks:
        return True
    for i in range(len(cores)):
        if cores[i] >= tasks[0]:
            cores[i] -= tasks[0]
            if solve(cores, tasks[1:]):
                return True
            cores[i] += tasks[0]
    return False

cores = [10, 7]
tasks = [7, 3, 2, 2, 1]
print(solve(cores, tasks))

Đầu vào

[10, 7], [7, 3, 2, 2, 1]

Đầu ra

True