Question

Given a value V, we need to make change for V paisa’s with the fewest number of coins, using the coins in the given coin denominations, coins []={C1, C2, .. , Cn}.

1. Design a greedy technique ‘pseudo-code’ for the ‘Coin change’ problem
2. With an example prove that your pseudo-code is a greedy technique.
3. With an example discuss whether your pseudo-code is an optimal solution for this problem.

Note: Assume unlimited supply of coins of given denominations.

Answer 1

1)

1) Initialize result as empty.
2) find the largest denomination that is 
   smaller than V.
3) Add found denomination to result. Subtract 
   value of found denomination from V.
4) If V becomes 0, then print result.  
   Else repeat steps 2 and 3 for new value of V

2)

3)

For example, the greedy approach doesn’t work for denominations {9, 6, 5, 1} and V = 11. It would give 9, 1 and 1. But we can use 2 denominations 5 and 6.