2

I'm trying to solve the "Coin Change Problem" by implementing a recursive backtracking algorithm which will analyze all possible outcomes and show the optimal combination of coins. Unfortunately, I have no idea how I can compare the different branches of the tree diagram that is being created. Any idea?

public class CoinChange_Backtracking {
        
    static int[] coins = {3, 2, 1};
    static int amount = 3;
    static int index_coins = 0;
    static LinkedList ll = new LinkedList();
    
    
    public static void main(String[] args) {
        //Start Recursion and display result.
        ll = recursiveFunction(coins, amount, index_coins, ll);
        ll.print();
    }

    
    public static LinkedList recursiveFunction(int[] coins, int amount, int index_coins, LinkedList ll) {
        //The current coin is being omitted. (If index_coins + 1 is still within range.)
        if ((index_coins + 1) < coins.length) {
            recursiveFunction(coins, amount, index_coins + 1, ll);
        }
        
        //The current coin is not being omitted. (If there is still some change left and value of change isn't lower than value of current coin.)
        if (amount != 0) {
            if (amount >= coins[index_coins]) {
                ll.add(coins[index_coins]);
                ll = recursiveFunction(coins, amount - coins[index_coins], index_coins, ll);
            }
        }
        return ll;
    }
}
Will Ness
  • 70,110
  • 9
  • 98
  • 181
Mar
  • 43
  • 3
  • I'm either overlooking something or your code does not generate a tree structure, but rather a list with coin values, without a way to distinct between 'branches'. I'd suggest generating an actual tree (List of Lists or see https://stackoverflow.com/questions/3522454/how-to-implement-a-tree-data-structure-in-java). After that 'just' count the number of coins in each solution and take the lowest coin amount as the best solution (maybe multiple solutions). – Eskapone Jun 09 '22 at 10:26
  • What do you mean by saying *optimal combination*? What are the criteria? – Alexander Ivanchenko Jun 09 '22 at 10:36
  • @AlexanderIvanchenko Shortest possible list of coin values. For instance, if the amount is 5, the optimal combination would be 3+2, not 3+1+1 or 2+1+1+1 or 1+1+1+1+1. – Mar Jun 09 '22 at 10:53
  • Ah yes, with the coins `{5,4,1}` and the target value of 8 the optimal solution is 4+4, but the greedy algorithm will find 5+1+1+1 first. – Will Ness Jun 29 '22 at 15:29

0 Answers0