  This paper analyzes a necessary and sufficient condition for the
change-making problem to be solvable with a greedy algorithm. The change-making
problem is to minimize the number of coins used to pay a given value in a
specified currency system. This problem is NP-hard, and therefore the greedy
algorithm does not always yield an optimal solution. Yet for almost all real
currency systems, the greedy algorithm outputs an optimal solution. A currency
system for which the greedy algorithm returns an optimal solution for any value
of payment is called a canonical system. Canonical systems with at most five
types of coins have been characterized in previous studies. In this paper, we
give characterization of canonical systems with six types of coins, and we
propose a partial generalization of characterization of canonical systems.
