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

ধরুন, 0 থেকে n-1 পর্যন্ত n নম্বর হোস্টেল কক্ষ রয়েছে। হোস্টেলের কক্ষের ছাত্ররা অন্য কক্ষে স্থানান্তর করতে চায় এবং তারা তা করার জন্য বেশ কিছু অনুরোধ করে। কোনো ছাত্রাবাসের আসন খালি থাকে না, স্থানান্তরের অনুরোধ শুধুমাত্র তখনই বিবেচনা করা হয় যদি অন্য একজন ছাত্র স্থানান্তর করতে ইচ্ছুক ছাত্রের জায়গায় নেয়। সুতরাং, অনুরোধের পরিপ্রেক্ষিতে, আমাদের খুঁজে বের করতে হবে কতগুলি অনুরোধ সন্তুষ্ট হতে পারে।

সুতরাং, যদি ইনপুট n =3 এর মত হয়, অনুরোধ =[[0,2],[1,0],[2,1]], তাহলে আউটপুট হবে 3।

0 কক্ষের ছাত্রটি 2 কক্ষে স্থানান্তরিত হয়।

1 কক্ষের ছাত্রটি 0 নং কক্ষে স্থানান্তরিত হয়।

2 কক্ষের ছাত্রটি 1 কক্ষে স্থানান্তরিত হয়।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• k-এর জন্য অনুরোধের রেঞ্জের আকার -1, 1 দ্বারা হ্রাস করুন, করুন

  • (0 থেকে অনুরোধের আকার এবং k) সমস্ত সংমিশ্রণে c-এর জন্য, করুন

    • d :=মান 0

      ধারণকারী n আকারের একটি নতুন অ্যারে

    • প্রতিটি i এর জন্য c, do

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

আউটপুট

3