Giả sử, có n số phòng trọ được đánh số từ 0 đến n-1. Các sinh viên trong các phòng trọ muốn chuyển đến một phòng khác, và họ đặt ra một số yêu cầu để thực hiện điều đó. Không có chỗ ngồi nào của ký túc xá còn trống, yêu cầu chuyển chỉ được thực hiện nếu một sinh viên khác thay thế chỗ của sinh viên sẵn sàng chuyển đến. Vì vậy, với các yêu cầu, chúng tôi phải tìm ra bao nhiêu yêu cầu có thể được đáp ứng.
Vì vậy, nếu đầu vào giống như n =3, yêu cầu =[[0,2], [1,0], [2,1]], thì đầu ra sẽ là 3.
Sinh viên ở phòng 0 chuyển sang phòng 2.
Sinh viên ở phòng 1 chuyển sang phòng 0.
Sinh viên ở phòng 2 chuyển sang phòng 1.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
đối với k trong phạm vi kích thước yêu cầu đến -1, giảm đi 1, thực hiện
-
đối với c trong tất cả các kết hợp của (0 đến kích thước yêu cầu và k), thực hiện
-
d:=một mảng mới có kích thước n chứa giá trị 0
-
cho mỗi tôi trong c, làm
-
d [yêu cầu [i, 0]]:=d [yêu cầu [i, 0]] - 1
-
d [yêu cầu [i, 1]]:=d [yêu cầu [i, 1]] + 1
-
-
nếu không có mục nào trong d là đúng, thì
-
trả lại k
-
-
-
-
trả về 0
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
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