Question

Greedy algorithm for the minimum coin change problem (the number of required coins is given)

function parameters :

- int amount = 20

- int Coins[] = [1, 5, 11, 25]

- int requiredCoins = 4

Expected result = 5,5,5,5,

****algorithm should be greedy, and find optimal solution***

You can provide the program or the algorithm

Answer 1

In this set of given coins, following greedy algorithm will give optimal result:-

1. Given amount amount N, perform division by coin highest denomination I.e. 25 and store the value of N/25 as number of coins of denomination 25.

2. If N%25 ==0 then stop else set N = N%25 and repeat the task for value 11 and so on till the reminder is zero.

Below is the formal C code, in which starting from highest index n-1 of array Coins, we are dividing it by denomination and store the quotient as the number of coins of that denomination. Then reminder of the division we are storing. If reminder is zero then return result , else repeat the process with lower denomination coin.

int Number_of_Coins(int amount, int Coins[], int n)

{

int k; //used as iterator

int result = 0; //this will store total number of coins

for (k=n-1 ; k>=0 ; k--) //iteration from highest denomination

{

result = result + amount / Coins[k] ;

amount = amount % Coins[k]; //remaining amount left

if (amount==0) //then return the result

return (result);

}

}

Note that above program will work and given optimal result for the given Coins[] = [1, 5, 11, 25] and not always. Greedy algorithm will not work for all denominations. For general case, we have to use dynamic programming approach.