1. In the USA, the denominations of currency are penny, nickel, dime, quarter, o
ID: 3690457 • Letter: 1
Question
1. In the USA, the denominations of currency are penny, nickel, dime, quarter, one dollar, two dollar, ve dollar, ten dollar, twenty dollar, fty dollar and one hundred dollar. It is always possible to make change for an X amount of dollars. Suppose that in a hypothetical country, the denominations of currency are d1,d2,···,dn.
The problem is given an X amount, we want to know if it is possible to make change for X using these denominations.
Example: let us suppose the denominations are 5,7,9. Then, if X = 17, then the answer is yes. It’s possible to make change for 17 with a combination of 5+5+7. On the other hand, if X = 13, then the answer is no.
The input is a list d of denominations and X, the amount to make change for. The output should be True of False.
Write a python program that performs this task.
Explanation / Answer
This question is similiar like this:
Given a value N, if we want to make change for N cents, and we have infinite supply of each of D = { d1, d2, .. , dm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.
For example, for N = 4 and D = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and D = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.
So, if number of ways to make change is ZERO(0) : it is not possible to make change.
# Dynamic Programming Python implementation of Coin Change problem
def count(S, m, n):
# We need n+1 rows as the table is consturcted in bottom up
# manner using the base case 0 value case (n = 0)
table = [[0 for x in range(m)] for x in range(n+1)]
# Fill the enteries for 0 value case (n = 0)
for i in range(m):
table[0][i] = 1
# Fill rest of the table enteries in bottom up manner
for i in range(1, n+1):
for j in range(m):
# Count of solutions including S[j]
x = table[i - S[j]][j] if i-S[j] >= 0 else 0
# Count of solutions excluding S[j]
y = table[i][j-1] if j >= 1 else 0
# total count
table[i][j] = x + y
return table[n][m-1]
# Driver program to test above function
arr = [5, 7, 9]
m = len(arr)
n = 13
if count(arr, m, n) != 0:
print "TRUE"
else:
print "FALSE"
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.