Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.

Related Articles:

• Memcomputing NP-complete problems in polynomial time using polynomial resources and collective state Read more...

• Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to Read more...

• Developing an applied algorithm for multi-trip vehicle routing problem with time windows in urban wa Read more...

• Decision making at the time of ICD generator change: patients' perspectives.

• A Two-Stage Multiobjective Evolutionary Algorithm for Multiobjective Multidepot Vehicle Routing Prob Read more...

A polynomial-time algorithm for the change-making problem

David Pearson - No affiliation found

2005/05/01 Short communication DOI: 10.1016/j.orl.2004.06.001 Journal: Operations Research Letters

Abstract:

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.