Combinatorics of the change-making problem

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.

18 pages, 4 figures Added a partial proof of conjecture 7.6 + some minor changes

References in corpus (1)

• Canonical Coin Systems for Change-Making Problems

Cited by in corpus (7)

• A Combinatorial Approach to Frobenius Numbers of Some Special Sequences (Complete Version)
• The Frobenius Formula for $A=(a,ha+d,ha+b_{2}d,...,ha+b_{k}d)$
• Totally Greedy Sequences Defined by Second-Order Linear Recurrences With Constant Coefficients
• Characterization of canonical systems with six types of coins for the change-making problem
• On the Frobenius Number and Genus of a Collection of Semigroups Generalizing Repunit Numerical Semigroups
• Solving Equations on Discrete Dynamical Systems (Extended version)
• What's in YOUR wallet?