# When change making problem has an optimal greedy solution?

A well-known Change-making problem, which asks

how can a given amount of money be made with the least number of coins of given denominations

for some sets of coins (50c, 25c, 10c, 5c, 1c) will yield an optimal solution by using a greedy algorithm (grab the highest value coin). For some other sets one have to use a dynamic programming.

Is there any way to prove whether for a given set of coins a greedy solution will always yield an optimal solution? Coin denomination can be any natural number (not only smaller then 100) and there can be any number of different coin denominations.

Suppose the set of coin denominations is $\{a_1,\ldots,a_n\}$ where $a_1>\ldots>a_n=1$. Let $S$ be the the given amount of money. Define $m_t=\lceil a_{t-1}/a_t\rceil$ and $S_t=m_ta_t$. Let $Opt(S)$ (respectively $G(S)$) denote the number of coins used in an optimal (respectively,the greedy) solution. Then we have the following theorem:

If $\ \ \ S_t<a_t-2 \$ for all $t\in\{3,\ldots,n\}\ \ \$ then
$Opt(S)=G(S) \quad$ iff $\quad G(S_t)\leq m_t \ \$ (for all $t\in\{2,\ldots,n\}$)

There is a simpler version which states only the sufficient condition:

$Opt(S)=G(S) \quad$ if $\quad G(S_t-a_{t-1})\leq m_t-1 \ \$ (for all $t\in\{2,\ldots,n\}$)

Let $C = \langle c_1, \ldots, c_n \rangle$ be the set of coin denominations in a sorted order (that is, $i \le j \to c_i \le c_j$). Let $V = \sum_{i=1}^{n-1} c_i$ (that is, sum of everything except for the largest coin). Now, for any integer $k > V \cdot c_n$, I claim that in the optimal set of coins that sums exactly to $k$, there exists at least one coin of value $c_n$ (the max coin). To see this, by pigeonhole principle there exists at least one coin $c_i$ that appears at least $c_n$ times in this set (otherwise their sum cannot exceed $V \cdot c_n$). Replace these $c_n$ coins with $c_i$ coins of value $c_n$, and we arrive at a contradiction.

Thus, we only need to check for all integers between $1$ and $V \cdot c_n$, inclusively, whether the greedy solution is optimal to sum to them, since we know that for all $k > V \cdot c_n$, an optimal solution will consist of multiple $c_n$ coins until the remaining value drops under or equal to $V \cdot c_n$.

The paper by Pearson, "A Polynomial-Time Algorithm for the Change-Making Problem", Operation Research Letters 33:3 (may 2005), pp. 231-234 (an earlier technical report is here) gives the most efficient algorithm to check this to date.