# Can the algorithm be optimized?

I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach with mermoization and a bottom up using dynamic programming. Even the brute force apporach always starts using a top down approach breaking the problem down into smaller sub problems and then caching.

However, I have written the following algorithm that is not optimized to do the same but cannot figure out how to apply memoization. Is it even possible?

My basic algorithm is I start from sum = 0 and keep count of how many coins I have used by adding coin values and then returning the minimum count.

//function is called with sum = 0, coins = 0 and minCoins = Integer.MAX_VALUE
//coins[] contains the different coin denominations and target is the desired amount
// count is the number of coins that have been used

public static int makeChangeBacktracking(int sum, int[] coins, int target, int count, int minCoins) {

if(sum == target) {
return count;
}

for(int coin : coins) {
//choose
sum+= coin;
//explore
if(sum <= target) { //if it is greater than the target then why recurse???
int c = makeChangeBacktracking(sum, coins, target, count + 1, minCoins);
if(minCoins > c) {
minCoins = c;
}
//undo
sum-= coin;
}
}
return minCoins;
}


I would like to apply any technique to improve the run time of the above algorithm. A clear explanation of whether or not memoization or other optimization techniques can be applied to this to speed up would be helpful.

• This problem is known as the Change-making Problem. See the related wikipage: en.wikipedia.org/wiki/Change-making_problem . – STanja Jun 8 at 11:28
• Thanks but the link doesn't explain going from sum 0 and then picking coins and any optimization for it. Can you provide an explanation? – Spindoctor Jun 8 at 12:27

A simple and efficient algorithm would be (correct me if I'm wrong):

1) Find the biggest valued coin just below that particular amount
2) Do the same thing with amount - coin_chosen
3) Repeat until convergence

Does this solve your problem?

e.g Available coins: 1p,2p,5p,10p,20p,50p,£1 ...
47p -> -20p -> 27p -> -20p -> 17p -> -10p -> 7p -> -5p -> 2p -> -2p -> 0p

There are other less efficient ways to do this like maybe using genetic algorithms but I guess this would be the quickest ...

• This is a greedy algorithm where its correctness depends on the available coins. Consider the coin set $\{1,4,9\}$ and the target sum of 12. By your approach, we need 4 coins: one 9, three times 1. The optimal number is 3 coins. – STanja Jun 8 at 11:25
• thanks but that is a greedy approach and the brute force will not give the true minimum number of coins. – Spindoctor Jun 8 at 12:28
• What do you mean with "and the brute force will not give the true minimum number of coins"? – STanja Jun 8 at 13:11
• @STanja This approach works for the standard coin system 1,2,5,10,20,50,100,etc. As most of the coins are multiples of 5 and 1,2,5 are "basically primes". But if there were an algorithm for any set of coins I'm all ears. However, I guess this is a semi NP problem. You could also use genetic algorithms ... – david david Jun 8 at 14:40
• Anyway STanja how would you get the number 3 with your set of coins? – david david Jun 8 at 14:55