পাইথনে কতগুলো ট্রান্সফার রিকোয়েস্ট পূরণ করা যায় তা খুঁজে বের করার প্রোগ্রাম

মান লেন n সংখ্যক হোস্টেল রুম আছে ০ থেকে n-1 পর্যন্ত নম্বর করা। হোস্টেলের ছাত্ররা অন্য রুমে ট্রান্সফার হতে চায়, এবং সে জন্য তারা অনেক রিকোয়েস্ট করে। কোনো হোস্টেল সিট খালি থাকে না, একটি ট্রান্সফার রিকোয়েস্ট তখনই নেওয়া হয় যখন অন্য একজন ছাত্র সেই রুমে আসতে রাজি হয়। তাই, রিকোয়েস্টগুলো দেওয়া থাকলে, আমাদের বের করতে হবে কতগুলো রিকোয়েস্ট পূরণ করা যায়।

উদাহরণস্বরূপ, ইনপুট n = 3, requests = [[0,2],[1,0],[2,1]] হলে আউটপুট হবে 3।

রুম ০-এর ছাত্র রুম ২-এ ট্রান্সফার হয়।

রুম ১-এর ছাত্র রুম ০-এ ট্রান্সফার হয়।

রুম ২-এর ছাত্র রুম ১-এ ট্রান্সফার হয়।

সমাধানের ধাপসমূহ (ব্যাকট্র্যাকিং / কোম্বিনেশন)

• k = requests-এর আকার থেকে ১ পর্যন্ত ১ কমানো হারে লুপ চালান:

  • c = requests-এর আকার থেকে k নেয়া সব কোম্বিনেশনের জন্য:

    • d := n আকারের অ্যারে ০ দিয়ে ফিল করে

    • c-এর প্রতিটি i এর জন্য:

      • d[requests[i][0]] -= 1

      • d[requests[i][1]] += 1

    • যদি d-এর কোনো আইটেম true না থাকে (অর্থাৎ সব ০), তবে:

      • 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