Trouble printing out denominations used in Minimum Change algorithm

Question

So I wrote a recursive algorithm for the problem of figuring out the least number of 'coins' of a particular set of denominations possible to arrive at a given sum. The algorithm seems to work, but because it's recursive, and calculates every possible option before choosing one or the other, I'm having a difficult time coming up with a way to print out the denominations used as well. So essentially I can calculate the least number of coins possible to use, but not which coins they are. Here's the code and the little main method I'm using to drive it. Any suggestions of streamlining the algorithm itself would also be welcome.

public class DynamicCoinChange {

    public static void main(String[] args) {
        int[] denoms = {1, 6, 10, 25};
        int numCoins = dynamicCoinChange(denoms, 18, 3);
        System.out.println(numCoins);
    }

    public static int dynamicCoinChange(int[] denoms, int amt, int start) {
        if (amt == 0 || start < 0) {
            return 0;
        } else if (amt == 1) {
            return 1;
        } else if (denoms[start] > amt || 
                dynamicCoinChange(denoms, amt, start-1) < 
                (1 + dynamicCoinChange(denoms, amt-denoms[start], start)) &&
                !(dynamicCoinChange(denoms, amt, start-1) == 0)) {
            return dynamicCoinChange(denoms, amt, start-1);
        } else {
            return 1 + dynamicCoinChange(denoms,amt-denoms[start], start);
        }
    }
}

Answer 1

We need to know two pieces of information:

• when a coin is chosen for the optimal solution
• which coin was chosen for the optimal solution

According to your algorithm, we know that we select a coin whenever you return 1. We also know that the coin chosen at that the index of the coin chosen is start. Thus, we have information to solve this problem.

Since performance isn't a problem here, we will simply pass a coins parameter that is filled as the coins are selected.

public static int dynamicCoinChange(int[] denoms, int amt, int start, ArrayList<Integer> coins) {
    if (amt == 0 || start < 0) {
        return 0;
    } else if (amt == 1) {
        coins.add(1);
        return 1;
    } else if (denoms[start] > amt 
            // Note that these calls are not guaranteed to be in our solution
            // Thus, we make a copy to prevent the calls from modifying our solution
            || dynamicCoinChange(denoms, amt, start-1, new ArrayList<Integer>(coins)) < 
                (1 + dynamicCoinChange(denoms, amt-denoms[start], start, new ArrayList<Integer>(coins))) 
            && !(dynamicCoinChange(denoms, amt, start-1, new ArrayList<Integer>(coins)) == 0)) {
        return dynamicCoinChange(denoms, amt, start-1, coins);
    } else {
        coins.add(denoms[start]);
        return 1 + dynamicCoinChange(denoms,amt-denoms[start], start, coins);
    }
}

Since this requires us to change our method signature, we must also modify our driver:

public static void main(String[] args) {
    int[] denoms = {1, 6, 10, 25};
    ArrayList<Integer> coins = new ArrayList<Integer>();
    int numCoins = dynamicCoinChange(denoms, 7, 3, coins);
    for (Integer coin : coins)
        System.out.println(coin);
    System.out.println(numCoins);
}

At the end of the recursive calls, coins should contain the list of coins chosen in chronological order.

Answer 2

The Minimum Change problem need not be programmed recursively. It can be programmed in a simpler iterative fashion.

int[] denoms = { 1, 6, 10, 25 };
int amt = 18;
double[] min = new double[ amt + 1 ];

for( int i = 1; i < min.length; i++ ) { // We're keeping min[ 0 ] as 0/
    min[ i ] = Double.POSITIVE_INFINITY;
}

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

   for( int j = 0; j <= N - 1; j++ ) {

       if( denoms[ j ] <= i && min[ i - denoms[ j ] ] + 1 < min[ i ] )
           min[ i ] = min[ i - denoms[ j ] ] + 1;

   }
}

Here, your solution would be in entry min[amt].