[math-fun] Greedy Change

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 "Truth is just truth -- You can't have opinions about the truth." - Peter Schickele, from P.D.Q. Bach's oratorio "The Seasonings"