Affordable Access

Publisher Website

Combinatorics of the change-making problem

Authors
Journal
European Journal of Combinatorics
0195-6698
Publisher
Elsevier
Publication Date
Volume
31
Issue
1
Identifiers
DOI: 10.1016/j.ejc.2009.05.002
Disciplines
  • Computer Science

Abstract

Abstract We investigate the structure of the currencies (systems of coins) for which the greedy change-making algorithm always finds an optimal solution (that is, a one with minimum number of coins). We present a series of necessary conditions that must be satisfied by the values of coins in such systems. We also uncover some relations between such currencies and their sub-currencies.

There are no comments yet on this publication. Be the first to share your thoughts.