পাইথনে কয়েন এবং পরিমাণের সাথে আমরা কতগুলি স্বতন্ত্র মুদ্রা যোগ করতে পারি তা খুঁজে বের করার প্রোগ্রাম?

ধরুন আমাদের কাছে কয়েন নামক মানের একটি তালিকা এবং একই দৈর্ঘ্যের পরিমাণ নামে আরেকটি তালিকা রয়েছে। ith কয়েনের মান হল কয়েন[i] এবং বর্তমানে আমাদের কাছে ith কয়েনের পরিমাণ[i] সংখ্যা রয়েছে। এই কয়েনের অ-খালি গোষ্ঠী ব্যবহার করে আমরা কতগুলি স্বতন্ত্র মুদ্রা সমষ্টির মান পেতে পারি তা খুঁজে বের করতে হবে।

সুতরাং, ইনপুট যদি কয়েনের মত হয় =[1, 2, 5] পরিমাণ =[1, 2, 1], তাহলে আউটপুট হবে 10, যেমন আমাদের নিম্নলিখিত স্বতন্ত্র মুদ্রার যোগফল [1] =1, [2] থাকতে পারে। =2, [1,2] =3, [2,2] =4, [5] =5, [1,5] =6, [2,5] =7, [1,2,5] =8 , [2,2,5] =9, [1,2,2,5] =10।

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

একটি ফাংশন rec() সংজ্ঞায়িত করুন। এটি i, res

if i is same as size of coins , then
   return
for k in range 0 to quantities[i] + 1, do
   cur := res + k * coins[i]
   insert cur into fres
   rec(i + 1, cur)
From the main method, do the following:
fres := a new set
rec(0, 0)
return size of fres - 1

উদাহরণ

class Solution:
   def solve(self, coins, quantities):
      def rec(i, res):
         if i == len(coins):
            return
         for k in range(0, quantities[i] + 1):
            cur = res + k * coins[i]
            fres.add(cur)
            rec(i + 1, cur)

      fres = set()
      rec(0, 0)
      return len(fres) - 1

ob = Solution()
coins = [1, 2, 5]
quantities = [1, 2, 1]
print(ob.solve(coins, quantities))

ইনপুট

[1, 2, 5], [1, 2, 1]

আউটপুট

10