1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ This problem is known as the Change-making Problem. See the related wikipage: en.wikipedia.org/wiki/Change-making_problem . $\endgroup$
    – STanja
    Jun 8, 2020 at 11:28
  • $\begingroup$ 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? $\endgroup$
    – Spindoctor
    Jun 8, 2020 at 12:27
  • $\begingroup$ Currently the fastest solutions to the unbounded change-making problem are branch-and-bound algorithms with additional optimizations (such as partial/full memoization). See here for one example: stackoverflow.com/a/45121962/109122 $\endgroup$
    – RBarryYoung
    Oct 15, 2021 at 12:03

1 Answer 1

Reset to default
-2
$\begingroup$

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 ...

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ 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. $\endgroup$
    – STanja
    Jun 8, 2020 at 11:25
  • $\begingroup$ thanks but that is a greedy approach and the brute force will not give the true minimum number of coins. $\endgroup$
    – Spindoctor
    Jun 8, 2020 at 12:28
  • $\begingroup$ What do you mean with "and the brute force will not give the true minimum number of coins"? $\endgroup$
    – STanja
    Jun 8, 2020 at 13:11
  • $\begingroup$ @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 ... $\endgroup$
    – david david
    Jun 8, 2020 at 14:40
  • $\begingroup$ Anyway STanja how would you get the number 3 with your set of coins? $\endgroup$
    – david david
    Jun 8, 2020 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.