Minimum Coin Changing Problem

Given a sets of coins values (a1,a2...an) to make change of an amount of money value S. What is the minimum coin to be sum up equals to S.

sets of coin = 1,2,5,10,20,50,100
amount of money S = 21.

possible sum:
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
2+2+2+2+2+2+2+2+2+2+1
2+2+2+2+2+5+5+1
10+5+2+2+1+1
5+5+5+5+1
10+5+5+1
10+10+1
20+1 <--- minimum coins

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

public class MinimumCoinChange { public static void main(String[] args) { int n = 21; int[] sets = new int[] { 1, 2, 5, 10, 20, 50, 100 }; int sum = 0; while (n > 0) { int max = sets[0]; //find list of minumum coin change (unsort coins list) //for (int x = 0; x < sets.length; x++) { // if (sets[x] >= max && sets[x] <= n) // max = sets[x]; //} //find list of minumum coin change (sorted coins list) for (int x = sets.length - 1; x >= 0; x--) { if (sets[x] <= n) { max = sets[x]; break; } } System.out.println(max); n = n - max; } } }