[Math] When change making problem has an optimal greedy solution

algorithmslinear programmingoptimization

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.

Best Answer

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\}$)

Related Question