The greedy algorithm is pretty straightforward. To find the counter-example, consider denominations that are primes.