Don't be Greedy be Dynamic

If you are given unlimited number of coins of values V1, V2,… Vn etc and asked to find the minimum number of coins needed to create a Sum S then what would be the solution you would come up with ?

To better illustrate take the typical example, if you are given unlimited supplies of coins value 1, 2 and 5 and asked to create values of 8. Then one solution can be 8 = 8 coins of value 1 or 8 = 4 coins of value 2 etc but the solution that uses minimum number of coins overall would be 8 = 1 coin of 5 + 1 coin of 2 + 1 coin of 1.

Being Greedy

When I looked at it for the first time I thought the easiest way to solve this would be to act greedy.

Sort the coins in descending order with maximum valued coin being first. If number of coins is N then

For c = 1 to N

1. Take the value of coin at index 'c' and see how many times it would fit in the Sum required.
2. Find out the modulo of the Sum with value of coin at index 'c'
3. Repeat the calculations 1 and 2 for the next most valued coin on the modulo value got in step 2.

Sum of values obtained in 1 would be the number of coins required.

Applying this to get a value of 8 the steps would be

Loop1 = 5 will fit in 8 only 1 time, 8 mod 5 = 3

Loop2 = 2 will fit in 3 only 1 time, 3 mod 2 = 1

Loop3 = 1 will fit in 1 only 1 time, 1 mod 2 = 0

Number of coins needed = 3 !

Code in Java

private int[] coinArray = { 1, 2, 5};

private int minCoinsNeededToGetCount(int neededCount) {

int coinCountNeeded = 0;

int tempNeededCount = neededCount;

for(int k = coinArray.length-1; k >=0; k--) {

if(tempNeededCount >= coinArray[k]) {

int numCoinsOfThisTypeNeeded = (tempNeededCount - (tempNeededCount % coinArray[k])) / coinArray[k];

tempNeededCount = tempNeededCount - (numCoinsOfThisTypeNeeded * coinArray[k]);

coinCountNeeded = coinCountNeeded + numCoinsOfThisTypeNeeded;

}

}

return coinCountNeeded;

}

But is this the best and correct solution ?

Being Dynamic

Described as one of the two sledgehammers of the algorithms craft, Dynamic Programming is very powerful and can be used to solve a wide variety of problems.

The two major things to remember in Dynamic Programming is that we break the problem into a collection of sub problems to solve such that a solution to one sub problem depends on the solution of another smaller sub problem.

In plain recursion we solve the same sub problems again and again. One of the main differences that Dynamic Programming brings over plain recursion is that here we store the results of the sub problems and do not compute them again. This is called 'memoization'.

So Applying this how would our solution be ?

1. Coins for Sum 0 = 0
2. Coins for Sum 1 = 1 coin of Value 1+ No of coins for remaining Sum of 0= 1

-> Remaining sum 0 is got by Sum needed 1 minus coin value considered 1 = 0

3. Coins for Sum 2 = Min ( 1 coin of Value 1 + No of coins for Rem.Sum 1, 1 coin of value 2 + No of coins for Rem.Sum 0 ) = Min (2, 1) = 1 ;

-> Remaining sum 1 is got by Sum needed 2 minus coin value considered 1 = 1

-> Remaining sum 0 is got by Sum needed 2 minus coin value considered 2 = 0

4. Coins for Sum 3 = Min ( 1 coin of Value 1 + No of coins for Sum 2 , 1 coin of value 2 + No of coins for Sum 1 ) = Min (2, 2) = 2

So we take the sum required and find out the difference between that sum and various coin values and get small problems. The solution to those small sub problems are already available and we just use them to build bigger solutions.

private int[] coinArray = { 1, 2, 5};

private void findMinCoinsNeededForSum(int sum){

int coinCounts[] = new int[sum+1];

Arrays.fill(coinCounts, 999);

coinCounts[0] = 0;

for(int i = 1; i <= sum; i++) {

for(int j = 0; j <>

int stateToCheck = i - coinArray[j];

if(stateToCheck >= 0 && coinCounts[stateToCheck] + 1 <>

coinCounts[i] = coinCounts[stateToCheck] + 1;

}

}

}

int i = 0;

for(int value : coinCounts) {

System.out.println("for " + i++ + " coins needed " + value);

}

}

Somehow when I wrote these 2 I felt the greedy approach was more simpler to understand and that was the first thing that came to my mind. But is it the right thing?

Given coin values of 1, 4 and 5 and asked to compute a sum of 8 greedy returns a miserable minimum coin count needed of 4 - one 5 and three 1's. So there u have the clear winner !!

Subscribe to comments for this post