Pythonで満たすことができる転送要求の数を見つけるためのプログラム

0からn-1までの番号が付けられたn個のホステルの部屋があるとします。ホステルの部屋にいる学生は別の部屋に転校したいと思っており、それを行うためにいくつかのリクエストを出します。ホステルの空席はありません。転校を希望する学生の代わりに別の学生が就任した場合にのみ、転校のリクエストが処理されます。したがって、リクエストを考慮して、満たすことができるリクエストの数を見つける必要があります。

したがって、入力がn =3、requests =[[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 [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]]))

入力

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

出力

3