2. (Problem 8-7 in the Tertbook.) In the United States, coins have denominations

Question

2. (Problem 8-7 in the Tertbook.) In the United States, coins have denominations 1, 5, 10, 25, and 50 cents. Now, consider a country whose coins have denominations di, da, ..., dk. Let C(n) be the number of distinct ways for coins to add up to the value n. We want to compute C(n). For example, in a country whose denominations are {1,6,10), C(5) is 1, C(6) through C(9) are 2. C(10) is 3, and C (12) is 4. a) What is C(20), if the denominations are (1,6, 10)? (Show your work.) b) Give an efficient [dynamic programming) algorithm to compute C(n). The input to the algorithm is the set of denominations (di, d2, . dk) as well as the value of n. (Hint Think in terms of computing C(n,j), the number of ways that coins of just the first denominations (dd.. 4) can add up to n.)

Explanation / Answer

To find C(20) , given denominations {1,6,10}

#we consider first using 1 dnomination only i.e. either '1 or 6 or 10'

for "1" : only possible case is (1*20) ---1

for "6" : not possible

for "10" : its (10*2) ---1

#using 2 denominations i.e. ( 1&6 , 1&10 , 6&10 )

(1&6) : (6*1)+(1*14) , (6*2)+(1*8) , (6*3)+(1*2)    ---3

(1&10) : (10*1)+(1*10)    ---1

(6&10) : not possible

#using 3 denominations i.e (all 1, 6, 10)

(1&6&10) : (10*1)+(6*1)+(1*4)     --- 1

so on totaling the count we get there are 7 possible combinations .

###########################################################

(b)

#The following code is written in python3 . it performs the same operation as asked by you

def count(D, m, n ):

   # If n is 0 then there is 1
   # solution (do not include any coin)
   if (n == 0):
       return 1

   # If n is less than 0 then no
   # solution exists
   if (n < 0):
       return 0;

   # If there are no coins and n
   # is greater than 0, then no
   # solution exist
   if (m <=0 and n >= 1):
       return 0

   # count is sum of solutions (i)
   # including D[m-1] (ii) excluding D[m-1]
   return count( D, m - 1, n ) + count( D, m, n-D[m-1] );

# Driver program to test above function. It takes input as of part (a) of the question.
arr = [1,6,10]
m = len(arr)
print(count(arr, m,20))

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.