Chương trình tìm số yêu cầu chuyển phòng có thể thỏa mãn trong Python

Mô tả bài toán

Có n phòng ký túc xá. Sinh viên muốn chuyển phòng, đặt yêu cầu [from, to]. Yêu cầu chỉ được thỏa mãn nếu có sinh viên khác nhận phòng cũ. Tìm số yêu cầu tối đa có thể thỏa mãn cùng lúc.

Ví dụ

n = 3, requests = [[0,2],[1,0],[2,1]] -> 3 (chu trình 0->2, 1->0, 2->1).

Giải thuật (Brute Force Subset)

1. Duyệt k từ len(requests) xuống 1.
2. Với mỗi tổ hợp k yêu cầu: kiểm tra cân bằng net flow tại mỗi phòng (số vào = số ra).
3. Nếu tìm thấy tổ hợp cân bằng -> trả về k.

Triển khai Python

from itertools import combinations

def solve(n, requests):
    for k in range(len(requests), 0, -1):
        for c in combinations(range(len(requests)), k):
            d = [0] * n
            for i in c:
                d[requests[i][0]] -= 1
                d[requests[i][1]] += 1
            if not any(d):
                return k
    return 0

print(solve(3, [[0, 2], [1, 0], [2, 1]]))

Đầu vào

3, [[0,2],[1,0],[2,1]]

Đầu ra

3