दिए गए सिक्कों से n रुपये प्राप्त करने के तरीके ढूंढने का पायथन प्रोग्राम

मान लीजिए हमें (1, 2, 5 और 10) मूल्यवर्ग के सिक्के दिए गए हैं। हमें यह ढूंढना है कि इन मूल्यवर्गों का उपयोग करके n को कितने तरीकों से व्यवस्थित किया जा सकता है। हमारे पास count नामक 4 एलिमेंट्स की एक ऐरे है, जहां count[0] 1 के सिक्कों की संख्या दर्शाता है, count[1] 2 के सिक्कों की संख्या दर्शाता है और इसी तरह।

तो, यदि इनपुट n = 27 count = [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

इत्यादि...

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

denom := [1,2,5,10]
A := आकार (n + 1) की एक ऐरे और 0 से भरें
B := A से एक नई सूची
i के लिए 0 से (count[0] और n का न्यूनतम) तक की रेंज में, करें
- A[i] := 1
i के लिए 1 से 3 तक की रेंज में, करें
- j के लिए 0 से count[i] तक की रेंज में, करें
  - k के लिए 0 से n + 1 - j *denom[i] तक की रेंज में, करें
    - B[k + j * denom[i]] := B[k + j * denom[i]] + A[k]
- j के लिए 0 से n तक की रेंज में, करें
  - 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]