Article ID Journal Published Year Pages File Type
10524096 Operations Research Letters 2005 4 Pages PDF
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
A polynomial-time algorithm for the change-making problem
Authors
,