A polynomial-time algorithm for the change-making problem

Optimally making change-representing a given value with the fewest coins from a set of denominations-is in general NP-hard. In most real money systems however, the greedy algorithm is optimal. We give a polynomial-time algorithm to determine, for a given coin system, whether the greedy algorithm is optimal.