পাইথন প্রোগ্রাম প্রদত্ত কয়েন দিয়ে n টাকা পাওয়ার উপায় খুঁজে বের করতে

ধরুন আমরা মূল্যবোধের একটি মুদ্রা দিয়েছি (1, 2, 5 এবং 10)। এই আধিপত্যগুলি ব্যবহার করে আমরা কতগুলি উপায়ে n সাজাতে পারি তা আমাদের খুঁজে বের করতে হবে। আমাদের কাছে 4টি উপাদান সহ গণনা নামে একটি অ্যারে রয়েছে, যেখানে গণনা[0] 1-এর কয়েনের সংখ্যা নির্দেশ করে, গণনা[1] 2 এবং আরও অনেক কিছুর মুদ্রার সংখ্যা নির্দেশ করে৷

সুতরাং, যদি ইনপুটটি n =27 গণনা =[8,4,3,2] এর মত হয়, তাহলে আউটপুট 18 হবে তাই 18টি সম্ভাব্য সমন্বয় রয়েছে তাদের মধ্যে কয়েকটি হল

10*2 + 5*1 + 2*1 =27
10*2 + 2*3 + 1*1 =27
10*1 + 5*3 + 2*1 =27
10*1 + 5*1 + 4*2 + 4*1 =27

ইত্যাদি...

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

ডিনম :=[1,2,5,10]
A :=আকারের একটি অ্যারে (n + 1) এবং 0 দিয়ে পূরণ করুন
B :=A থেকে একটি নতুন তালিকা
0 থেকে (সর্বনিম্ন গণনা [0] এবং n) রেঞ্জের জন্য, কর
- A[i] :=1
আমি 1 থেকে 3 রেঞ্জের জন্য, কর
- করুন
  - A[j] :=B[j]
  - B[j] :=0
প্রত্যাবর্তন A[n]

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

denom = [1,2,5,10]

def solve(n, count):
   A = [0 for _ in range(n+1)]
   B = list(A)
   for i in range(min(count[0], n) + 1):
      A[i] = 1
   for i in range(1, 4):
      for j in range(0, count[i] + 1):
         for k in range(n + 1 - j *denom[i]):
            B[k + j * denom[i]] += A[k]
      for j in range(0, n + 1):
         A[j] = B[j]
         B[j] = 0
   return A[n]

n = 27
count = [8,4,3,2]
print(solve(n, count))

ইনপুট

27, [8,4,3,2]