पायथन में कितने स्थानांतरण अनुरोधों को पूरा किया जा सकता है, यह जानने के लिए कार्यक्रम

मान लीजिए, हॉस्टल के कमरों की संख्या 0 से n-1 तक है। छात्रावास के कमरे के छात्र दूसरे कमरे में स्थानांतरित करना चाहते हैं, और वे ऐसा करने के लिए कई अनुरोध करते हैं। कोई छात्रावास की सीट खाली नहीं रहती है, स्थानांतरण अनुरोध पर तभी ध्यान दिया जाता है जब स्थानांतरण के इच्छुक छात्र की जगह कोई अन्य छात्र ले लेता है। इसलिए, अनुरोधों को देखते हुए, हमें यह पता लगाना होगा कि कितने अनुरोधों को पूरा किया जा सकता है।

इसलिए, यदि इनपुट n =3, अनुरोध =[[0,2], [1,0], [2,1]] जैसा है, तो आउटपुट 3 होगा।

कमरा 0 का छात्र कमरा 2 में स्थानान्तरित होता है।

कमरा 1 का छात्र कमरा 0 में स्थानांतरित होता है।

कमरा 2 के छात्र को कमरा 1 में स्थानांतरित किया जाता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• k के लिए अनुरोधों की श्रेणी आकार -1 तक, 1 से घटाएं, करें

  • सभी संयोजनों में सी के लिए (अनुरोधों के आकार और के अनुसार), करें

    • d :=आकार n की एक नई सरणी जिसमें मान 0 है

    • सी में प्रत्येक के लिए, करें

      • डी [अनुरोध [i, 0]]:=डी [अनुरोध [i, 0]] - 1

      • d[अनुरोध[i, 1]]:=d[अनुरोध[i, 1]] + 1

    • यदि d में से कोई भी आइटम सत्य नहीं है, तो

      • वापसी कश्मीर

• वापसी 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