Coin Change Problem: Suppose a country ABC’s currency has the following coins, a
ID: 3619537 • Letter: C
Question
Coin Change Problem:Suppose a country ABC’s currency has the following coins,
a. 3 cent
b. 6 cent
c. 9 cent
1. You have to find the solution of coin change problem using Dynamic
Programming approach for amount 12. [Your solution should have
minimum number of coins].
2. Find the solution of the above problem using Greedy Algorithm’s approach.
Hints:
o Your Table will have coins (denominations) as rows and values from 1 to
12 as columns. This problem is very similar to knapsack problem with the
difference that here value is count of coins and we will select minimum
coins count, you can see further details in handouts and video lecture.
o Since we want to minimize the number of coins used,
C[i, j] = min(C[i - 1, j], 1 + C[i, j - di])
o We will find the coins to be used in similar manner using separate table as
we found in Knapsack problem.
o For Greedy Approach you will take coin of highest value first.
Both question are related
Explanation / Answer
Question Details Coin Change Problem:Suppose a country ABC’s currency has the following coins,
a. 3 cent
b. 6 cent
c. 9 cent
1. You have to find the solution of coin change problem using Dynamic
Programming approach for amount 12. [Your solution should have
minimum number of coins].
2. Find the solution of the above ... TOTAL=12 THE PROBLEM IS TOO SIMPLE TO NEED DYNAMIC PROGRAMMING ANY WAY CALLING PROPOSALS AS P1,P2 ETC......WE HAVE P1 ......3+3+3+3=12...........NEEDS 4 COINS P2.......3+3+6=12...................NEEDS 3 COINS P3.......3+9=12...................... NEEDS 2 COINS P4.......6+6=12.........................NEEDS 2 COINS SO WE FIND P3 AND P4 ARE THE PROPOSALS REQUIRING MINIMUM NUMBER OF COINS Coin Change Problem:
Suppose a country ABC’s currency has the following coins,
a. 3 cent
b. 6 cent
c. 9 cent
1. You have to find the solution of coin change problem using Dynamic
Programming approach for amount 12. [Your solution should have
minimum number of coins].
2. Find the solution of the above ... TOTAL=12 THE PROBLEM IS TOO SIMPLE TO NEED DYNAMIC PROGRAMMING ANY WAY CALLING PROPOSALS AS P1,P2 ETC......WE HAVE P1 ......3+3+3+3=12...........NEEDS 4 COINS P2.......3+3+6=12...................NEEDS 3 COINS P3.......3+9=12...................... NEEDS 2 COINS P4.......6+6=12.........................NEEDS 2 COINS SO WE FIND P3 AND P4 ARE THE PROPOSALS REQUIRING MINIMUM NUMBER OF COINS Coin Change Problem:
Suppose a country ABC’s currency has the following coins,
a. 3 cent
b. 6 cent
c. 9 cent
1. You have to find the solution of coin change problem using Dynamic
Programming approach for amount 12. [Your solution should have
minimum number of coins].
2. Find the solution of the above ... TOTAL=12 THE PROBLEM IS TOO SIMPLE TO NEED DYNAMIC PROGRAMMING ANY WAY CALLING PROPOSALS AS P1,P2 ETC......WE HAVE P1 ......3+3+3+3=12...........NEEDS 4 COINS P2.......3+3+6=12...................NEEDS 3 COINS P3.......3+9=12...................... NEEDS 2 COINS P4.......6+6=12.........................NEEDS 2 COINS SO WE FIND P3 AND P4 ARE THE PROPOSALS REQUIRING MINIMUM NUMBER OF COINS