1,072 views

1 Answer

0 votes
0 votes

Part 1:

Greedy Algorithm to make change for a given value of n in terms of the given denominations: 25 cents, 10 cents, 5 cents and 1 cent. 

To minimize the no of coins start with the coins of maximum denomination (greedy for values). 

currentValue=n

denomination[]={25,10,5,1};

mincoins=0;

i=0;

while(currentValue!=0)

{

if(denomination[i]<currentValue)

{mincoins+=currentValue/denomination[i];

currentValue%=denomination[i];

}

++i;

}

By following this algo we will get the minimum number of coins by greedy approach.

Part 2:

To show that the greedy approach does not yield an optimal solution.

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.
 Hence proved that the greedy approach doesnot always yield a correct answer.