โปรแกรมหาจำนวนคำขอย้ายห้องที่ตอบสนองได้ใน Python

มีห้องพัก n ห้อง (0..n-1) นักเรียนขอย้าย requests[i]=[from, to] ไม่มีห้องว่าง คำขอจะดำเนินการได้ก็ต่อเมื่อมีคนย้ายเข้ามาแทนที่ หาจำนวนคำขอสูงสุดที่ตอบสนองได้

ตัวอย่าง: n=3, requests=[[0,2],[1,0],[2,1]] ผลลัพธ์ 3 (เป็น cycle)

วิธีแก้ปัญหา (Brute Force Subsets)

1. ลอง subset ของคำขอจากใหญ่ไปเล็ก (k = len(requests) .. 1)
2. ตรวจสอบว่า subset นั้นทำให้ net flow ทุกห้อง = 0 หรือไม่
3. เจอ subset ใด valid ก็คืนขนาดทันที

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

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]]))

อินพุต

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

เอาต์พุต

3