在Python中查找可以满足的转移请求的程序

假设有n个宿舍房间，编号从0到n-1。宿舍房间的学生想要转移到另一个房间，并提出了几个请求。如果没有宿舍座位空缺，仅当另一位学生取代愿意转移的学生时，才会处理转移请求。因此，给定这些请求，我们必须找出可以满足多少个请求。

因此，如果输入如下：n = 3，requests = [[0,2]，[1,0]，[2,1]]，则输出将为3。

房间0的学生转移到房间2。

房间1的学生转移到房间0。

房间2的学生转移到房间1。

要解决此问题，我们将遵循以下步骤 −

对于从请求的大小到-1的k范围内，递减1，做以下操作
- 对于(0到请求大小和k)的所有组合中的c，做以下操作
  - d：大小为n的新数组，其中包含值0
  - 对于c中的每个i，做以下操作
  - d[requests[i,0]]：= d[requests[i,0]] – 1
  - d[requests[i,1]]：= d[requests[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]]))