A polynomial-time algorithm for the change-making problem |
| |
| Authors: | David Pearson |
| |
| Institution: | BBN Technologies, 10 Moulton Street, Cambridge, MA 02138, USA |
| |
| 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: | Change-making Coin systems Greedy algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
