Calculate number of possible combinations to make $100 with all US denominations

Question

I know that this could be made much more efficient, I am just not sure as to how.

This program ignores the 100 dollar denomination to cut computation time in half and just starts totalcombinations at 1 to compensate. I'm fairly certain that there is some way that this could be made both more efficient and readable. If anyone has any clues as to how this could be achieved, your help would be much appreciated. I wouldn't recommend running this program in its current state with the intent of seeing it through to completion. On my computer it was at about 900,000,000 combinations after 48 hours. That brings to mind, how would I avoid letting the integer get too big, as I suspect it will.

package main;

public class Cycle {
    int penny = 0;
    int nickle = 0;
    int dime = 0;
    int quarter = 0;
    int halfdollar = 0;
    int onedollar = 0;
    int twodollar = 0;
    int fivedollar = 0;
    int tendollar = 0;
    int twentydollar = 0;
    int fiftydollar = 0;
    int onehundreddollar = 0;
    int fivehundreddollar = 0;
    int totalcombinations = 1;

    public void cycle() {
        while (onehundreddollar < 1) {
            if (penny < 10000) {
                penny++;
                checkandadd();
            }
            else {
                penny = 0;
                if (nickle < 2000) {
                    nickle++;
                    checkandadd();
                }
                else {
                    nickle = 0;
                    if (dime < 1000) {
                        dime++;
                        checkandadd();
                    }
                    else {
                        dime = 0;
                        if (quarter < 400) {
                            quarter++;
                            checkandadd();
                        }
                        else {
                            quarter = 0;
                            if (halfdollar < 200) {
                                halfdollar++;
                                checkandadd();
                            }
                            else {
                                halfdollar = 0;
                                if (onedollar < 100) {
                                    onedollar++;
                                    checkandadd();
                                }
                                else {
                                    onedollar = 0;
                                    if (twodollar < 50) {
                                        twodollar++;
                                        checkandadd();
                                    }
                                    else {
                                        twodollar = 0;
                                        if (fivedollar < 20) {
                                            fivedollar++;
                                            checkandadd();
                                        }
                                        else {
                                            fivedollar = 0;
                                            if (tendollar < 10) {
                                                tendollar++;
                                                checkandadd();
                                            }
                                            else {
                                                tendollar = 0;
                                                if (twentydollar < 5) {
                                                    twentydollar++;
                                                    checkandadd();
                                                }
                                                else {
                                                    twentydollar = 0;
                                                    if (fiftydollar < 2) {
                                                        fiftydollar++;
                                                        checkandadd();
                                                    }
                                                    else {
                                                        fiftydollar = 0;
                                                        if (onehundreddollar < 1) {
                                                            onehundreddollar++;
                                                            checkandadd();
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    public void checkandadd() {
            if (1*penny+5*nickle+10*dime+25*quarter+50*halfdollar+100*onedollar+200*twodollar+500*fivedollar+1000*tendollar+2000*twentydollar+5000*fiftydollar+10000*onehundreddollar == 10000) {
                totalcombinations = totalcombinations + 1;
                System.out.println(totalcombinations);
        }
    }
}

Answer 1

I'm fairly certain that there is some way that this could be made both more efficient and readable.

Yes! It's called Dynamic Programming, and it's awesome. It's a problem-solving methodology perfectly suited to your problem. Here is how it can be applied to your problem. Here and here are DP solutions to this problem in Java.

Here is an example solution (ref):

public int minChange(int[] denom, int targetAmount) {

    int actualAmount;
    int m = denom.length+1;
    int n = targetAmount + 1;
    int inf = Integer.MAX_VALUE-1;

    int[][] table = new int[m][n];
    for (int j = 1; j < n; j++) {
        table[0][j] = inf;
    }

    for (int denomPosition = 1; denomPosition < m; denomPosition++) {
        for (int currentAmount = 1; currentAmount < n; currentAmount++) {
            if (currentAmount - denom[denomPosition-1] >= 0) {
                actualAmount = table[denomPosition][currentAmount - denom[denomPosition-1]];
            } else {
                actualAmount = inf;
            }
            table[denomPosition][currentAmount] = Math.min(table[denomPosition-1][currentAmount], 1 + actualAmount);
        }
    }
    return table[m-1][n-1];
}