1
\$\begingroup\$

I have some code that will brute force solve the following problem:

Given a set of x coins and a target sum to reach, what is the fewest number of coins required to reach that target?

The code so far:

import java.util.ArrayList;
import java.util.Arrays;

public class coinsSum {
    public static int min = Integer.MAX_VALUE;
    public static int[] combination;
    public static final int TARGET = 59;

    public static void main(String[] args) {
        long start = System.nanoTime();

        int[] validCoins = new int[] {1, 2, 5, 10, 20};
        Arrays.sort(validCoins);
        int len = validCoins.length;

        ArrayList<Integer> maxList = new ArrayList<Integer>();
        for(int c : validCoins) {
            maxList.add(TARGET / c);
        }

        int[] max = new int[len];
        for(int i = 0; i < len; i++) {
            max[i] = maxList.get(i).intValue();
        }

        permutations(new int[len], max, validCoins, 0); // bread&butter

        if(min != Integer.MAX_VALUE) {
            System.out.println();
            System.out.println("The combination " + Arrays.toString(combination) + " uses " + min + " coins to make the target of: " + TARGET);
        } else {
            System.out.println("The target was not reachable using these coins");
        }

        System.out.println("TOOK: " + (System.nanoTime() - start) / 1000000 + "ms");
    }

    public static void permutations(int[] workspace, int[] choices, int[] coins, int pos) {
        if(pos == workspace.length) {
            int sum = 0, coinCount = 0;
            System.out.println("TRYING " + Arrays.toString(workspace));
            for(int a = 0; a < coins.length; a++) {
                sum += workspace[a] * coins[a];
                coinCount += workspace[a];
            }
            if(sum == TARGET) {
                // System.out.println(Arrays.toString(n)); //valid combinations
                if(coinCount < min) {
                    min = coinCount;
                    combination = workspace;
                    System.out.println(Arrays.toString(combination)+" uses " + min + " coins");
                }
            }
            return;
        }
        for(int i = 0; i <= choices[pos]; i++) {
            workspace[pos] = i;
            permutations(workspace, choices, coins, pos + 1);
        }
    }
}

This solution uses recursion. Is there any way to compute combinations in Java using loops?

What other improvements can be made to the algorithm?

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Your code is quite complicated. What makes it so complicated is that you have recursive calls interacting with global objects. This makes it almost impossible to understand what the state is at a given point.

When you write an algorithm in a recursive way, your goal should be to make the (smallest amount of) information go in one direction only through the method parameters (and no global state whatsoever) and to use return values to give the answer back.

This being said, let's try to see how to make this work.

This idea is quite simple here:

If I have to reach 59 with 1, 2, 5, 10, 20, I can try to take 0 time 20 and see how I can reach 59 with 1, 2, 5, 10. I can also try to take 1 time 20 and see how I can reach the remaining 39 with 1, 2, 5, 10. I can also try to take 2 times 20 and see how I can reach 19 with the remaining 1, 2, 5, 10.

I've reduced solving the problem to the resolution of smaller (because we have a smaller number of coins) problems. The question is "when should I stop ?". If you have reached the target, you can stop. If you have no coin left to try, you can stop;

Once expressing this with code, you can write:

import java.util.ArrayList;
import java.util.Arrays;

public class coinsSum {
    public static final int TARGET = 59;

    public static void main(String[] args) {
        long start = System.nanoTime();

        int[] validCoins = new int[] {1, 2, 5, 10, 20};
        Arrays.sort(validCoins);

        int min = permutations(TARGET, validCoins);
        System.out.println("TOOK: " + (System.nanoTime() - start) / 1000000 + "ms to find " + min);
    }

    public static int permutations(int target, int[] coins) {
        return permutations(target, coins, coins.length);
    }

    public static int permutations(int target, int[] coins, int array_size) {
        System.out.println("TRYING " + target + " with " + array_size + " different coins");
        assert target >= 0;
        assert array_size >= 0;
        assert array_size <= coins.length;
        if (target==0) // target is reached (in 0 coin)
            return 0;
        if (array_size == 0) // no more coins to reach a positive target
            return -1;
        array_size--;
        int coin = coins[array_size]; // let's consider the biggest coin
        int nb = target/coin; // and check how many times it fits in the target
        int sol = -1; // we haven't found a solution so far (Integer.MAX_VALUE would be another way to do this)
        for (int i = 0; i <= nb; i++) // let's try all possible values
        {
            // to check if we can reach the target with the other coins
            int sol_cand = permutations(target - i * coin, coins, array_size);
            if (sol_cand >= 0) // if we did
            {
                if (sol == -1 || sol_cand + i < sol) // and the new solution is better
                    sol = sol_cand + i; // then we are happy
            }
        }
        return sol;
    }
}

This is already 24 times faster than your example.

Now, you can try to add optimisations. A simple optimisation is to say that if you can reach the current target with the biggest coin, there's no need to go any further because you'll need more coins if you use smaller coins.

    int coin = coins[array_size]; // let's consider the biggest coin
    int nb = target/coin; // and check how many times it fits in the target
    if (nb * coin == target) // if it fits an exact number of time, we won't beat this
        return nb;

This makes the code 70 times faster on the example. (If you do so, the check that target == 0 is not relevant anymore because we'll always have target > 0).

Also, not a particular optimisation but if you want to use with Integer.MAX_VALUE just like you used to, you can rewrite the loop:

    int sol = Integer.MAX_VALUE; // we haven't found a solution so far (Integer.MAX_VALUE would be another way to do this)
    for (int i = 0; i <= nb; i++) // let's try all possible values
    {
        sol = Math.min(sol, i + permutations(target - i * coin, coins, array_size));
    }

This is as simple as it gets. Then, you can write unit tests to check that your code behaves the way you want. Finally, if you want to, you can consider various optimisations: using a cache to avoid computing the same thing multiple times, add conditions to stop the loop earlier, etc.

\$\endgroup\$
2
  • \$\begingroup\$ Good answer, what is sol_cand short for? \$\endgroup\$
    – spyr03
    Dec 30, 2014 at 17:41
  • 1
    \$\begingroup\$ It stands for "candidate solution". Not the greatest name now that I think about it :-P \$\endgroup\$
    – SylvainD
    Dec 30, 2014 at 17:43

Your Answer

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

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