पायथन में सिक्कों और मात्राओं के साथ हम कितने अलग-अलग सिक्के बना सकते हैं?

मान लीजिए कि हमारे पास सिक्कों नामक मूल्यों की एक सूची है और एक अन्य सूची है जिसे समान लंबाई की मात्रा कहा जाता है। 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() को परिभाषित करें। यह मैं, रेस

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