Python에서 만족할 수 있는 전송 요청 수를 알아내는 프로그램

<시간/>

0에서 n-1까지 번호가 매겨진 n개의 호스텔 객실이 있다고 가정합니다. 호스텔 방에 있는 학생들은 다른 방으로 옮기고 싶어하며 여러 차례 요청을 합니다. 빈 호스텔은 없으며, 전학을 희망하는 학생의 자리를 다른 학생이 대신할 경우에만 전학 요청이 처리됩니다. 따라서 요청이 주어지면 얼마나 많은 요청을 충족할 수 있는지 알아내야 합니다.

따라서 입력이 n =3, 요청 =[[0,2],[1,0],[2,1]]인 경우 출력은 3이 됩니다.

0번 방의 학생이 2번 방으로 이동합니다.

1번 방의 학생이 0번 방으로 이동합니다.

2번 방의 학생은 1번 방으로 이동합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

-1에 대한 요청 범위 크기의 k에 대해 1 감소, 수행
- (0에서 요청의 크기 및 k까지)의 모든 조합에서 c에 대해 다음을 수행하십시오.
  - d :=값 0을 포함하는 크기 n의 새 배열
  - c의 각 i에 대해 수행
    - d[요청[i, 0]] :=d[요청[i, 0]] - 1
    - d[요청[i, 1]] :=d[요청[i, 1]] + 1
  - d의 항목 중 어느 것도 참이 아닌 경우
    - k를 반환
0 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

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