A polynomial-time algorithm for the change-making problem
Review articleOpen access
2005/05/01 Short communication DOI: 10.1016/j.orl.2004.06.001
Journal: Operations Research Letters
AbstractOptimally 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.
Request full text