A polynomial-time algorithm for the change-making problem
Review articleOpen access
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.

Request full text

References (0)

Cited By (0)

No reference data.
No citation data.
Advertisement
Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.
Join for free!