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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.