Yes, there is an algorithm. See http://citeseer.ist.psu.edu/pearson94polynomialtime.html Jeffrey Shallit

...

I understand that with US coins of denominations (100, 50, 25, 10, 5, 1) cents, making change by the greedy algorithm (at each step select the largest possible coin) leads to optimal change (fewest coins) for all amounts.

There are other conceivable sets of denominations, e.,g, (10, 6, 1), where the greedy algorithm fails (for example, the greedy algorithm gives 18 = 10+6+1+1 whereas 18 = 6+6+6 uses fewer coins).

Is there an algorithm for determining if a given set of coins gives optimal change via the greedy algorithm?

- David W. Wilson