Given the coins with denominations 20,15,5 and 1 we have to generate a sumof 33 with the help of minimum number of coins.
Approach 1: Greedy Approach
In order to minimize the number of coins we have to choose the coins with the maximum denomination(more the denomination of the coin less is the number of the coins required). So the required value is 33. Coin with maximum denomination 20 is chosen as 20<33 we can use it so current value left=13 no. of coins=1. We can't use the coin with denomination 15 as current value is less than it. So the next highest denomination is 5 . We use 2 coins of denomination 5. total no of coins currently=3. value left=3. Next we use 3 coins of denomination 1 . total coins =3+3 =6.
By following greedy approach we get 6 coins.
Approach 2:Dynamic Programming
Dynamic programming uses the bottom up approach . We will check by which way we are getting the minimum number of coins starting with coins of :
Denomination 1: No. of coins=33
Denomination 1,5 : No. of coins=6+3=9
Denomination 1,5,15:No of Coins=2+3=5
Denomination 1,5,15,20: No. of Coins=1+2+3=6 but as the no. of coins we got in the previous steps are less we go with them.
So by following dynamic programming we get no of coins=5.
The difference is :6-5=1.