<p>The <a href="http://en.wikipedia.org/wiki/Change-making_problem" rel="nofollow noreferrer">wikipedia link</a> is sparse on details on how to decide if a greedy algorithm such as yours will work. A better reference is linked in this <a href="https://cs.stackexchange.com/questions/6552/when-can-a-greedy-algorithm-solve-the-coin-change-problem">CS StackExchange question</a>. Essentially, if the coin system is <em>canonical</em>, a greedy algorithm will provide an optimal solution. So, is [1, 2, 5, 10, 20] canonical? (using 10s of cents for units, so that the sequence starts in 1)</p>

<p>According to <a href="http://arxiv.org/PS_cache/arxiv/pdf/0809/0809.0400v1.pdf" rel="nofollow noreferrer">this article</a>, a 5-coin system is <em>non</em>-canonical if and only if it satisfies exactly one of the following conditions:</p>

<ul>
<li>[1, c2, c3] is non-canonical (false for [1, 2, 5])</li>
<li>it cannot be written as [1, 2, c3, c3+1, 2*c3] (true for [1, 2, 5, 10, 20])</li>
<li>the greedyAnswerSize((k+1) * c4) > k+1 with k*c4 &lt; c5 &lt; (k+1) * c4; in this case, this would require a k*10 &lt; 20 &lt; (k+1)*10; there is no integer k in that range, so this is false for [1, 2, 5, 10, 20].</li>
</ul>

<p>Therefore, since the greedy algorithm will not provide optimal answers (and even if it did, I doubt that it would work with limited coins), you should try dynamic programming or some enlightened backtracking:</p>

<pre><code>import java.util.HashSet;
import java.util.PriorityQueue;

public class Main {

    public static class Answer implements Comparable&lt;Answer&gt; {
        public static final int coins[] = {1, 2, 5, 10, 20};

        private int availableCoins[] = new int[coins.length];
        private int totalAvailable;
        private int totalRemaining;
        private int coinsUsed;

        public Answer(int availableCoins[], int totalRemaining) {
            for (int i=0; i&lt;coins.length; i++) {
                this.availableCoins[i] = availableCoins[i];
                totalAvailable += coins[i] * availableCoins[i];
            }
            this.totalRemaining = totalRemaining;
        }

        public boolean hasCoin(int coinIndex) { 
            return availableCoins[coinIndex] &gt; 0; 
        }

        public boolean isPossibleBest(Answer oldBest) {
            boolean r = totalRemaining &gt;= 0
                &amp;&amp; totalAvailable &gt;= totalRemaining
                &amp;&amp; (oldBest == null || oldBest.coinsUsed &gt; coinsUsed);
            return r;
        }

        public boolean isAnswer() {
            return totalRemaining == 0;
        }

        public Answer useCoin(int coinIndex) {
            Answer a = new Answer(availableCoins, totalRemaining - coins[coinIndex]);
            a.availableCoins[coinIndex]--;
            a.totalAvailable = totalAvailable - coins[coinIndex];
            a.coinsUsed = coinsUsed+1;
            return a;
        }

        public int getCoinsUsed() {
            return coinsUsed;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder("{");
            for (int c : availableCoins) sb.append(c + ",");            
            sb.setCharAt(sb.length()-1, '}');
            return sb.toString();
        }

        // try to be greedy first
        @Override
        public int compareTo(Answer a) {
            int r = totalRemaining - a.totalRemaining;
            return (r==0) ? coinsUsed - a.coinsUsed : r;
        }
    }        

    // returns an minimal set of coins to solve
    public static int makeChange(int change, int[] availableCoins) {
        PriorityQueue&lt;Answer&gt; queue = new PriorityQueue&lt;Answer&gt;();
        queue.add(new Answer(availableCoins, change));
        HashSet&lt;String&gt; known = new HashSet&lt;String&gt;();
        Answer best = null;
        int expansions = 0;
        while ( ! queue.isEmpty()) {
            Answer current = queue.remove();            
            expansions ++;
            String s = current.toString();
            if (current.isPossibleBest(best) &amp;&amp; ! known.contains(s)) {
                known.add(s);
                if (current.isAnswer()) {
                    best = current;
                } else {
                    for (int i=0; i&lt;Answer.coins.length; i++) {
                        if (current.hasCoin(i)) {
                            queue.add(current.useCoin(i));
                        }
                    }
                }
            }
        }
        // debug
        System.out.println("After " + expansions + " expansions");
        return (best != null) ? best.getCoinsUsed() : -1;
    }

    public static void main(String[] args) {
        for (int i=0; i&lt;100; i++) {
            System.out.println("Solving for " + i + ":"
                + makeChange(i, new int[]{100,5,2,5,1}));
        }
    }
}
</code></pre>
Least Coin Used Algorithm Java
<p>I am stuck on the coin denomination problem.</p>

<p>I am trying to find the lowest number of coins used to make up $5.70 (or 570 cents). For example, if the coin array is {100,5,2,5,1} (100 x 10c coins, 5 x 20c, 2 x 50c, 5 x $1, and 1 x $2 coin), then the result should be {0,1,1,3,1}
At the moment the coin array will consist of the same denominations ( $2, $1, 50c, 20c, 10c)</p>

<pre><code>public static int[] makeChange(int change, int[] coins) {

    // while you have coins of that denomination left and the total
    // remaining amount exceeds that denomination, take a coin of that
    // denomination (i.e add it to your result array, subtract it from the
    // number of available coins, and update the total remainder). –

    for(int i= 0; i&lt; coins.length; i++){
    while (coins[i] &gt; 0) {

        if (coins[i] &gt; 0 &amp; change - 200 &gt;= 0) {

            coins[4] = coins[4]--;
            change = change - 200;

        } else 

        if (coins[i] &gt; 0 &amp; change - 100 &gt;= 0) {

            coins[3] = coins[3]--;
            change = change - 100;

        } else

        if (coins[i] &gt; 0 &amp; change - 50 &gt;= 0) {

            coins[2] = coins[2]--;
            change = change - 50;

        } else

        if (coins[i] &gt; 0 &amp; change - 20 &gt;= 0) {

            coins[1] = coins[1]--;
            change = change - 20;

        } else

        if (coins[i] &gt; 0 &amp; change - 10 &gt;= 0) {

            coins[0] = coins[0]--;
            change = change - 10;

        }
    }

    }
    return coins;

}
</code></pre>

<p>I am stuck on how to deduct the values from coins array and return it.</p>

<p>EDIT: New code</p>