14
$\begingroup$

For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins.

However, for a coinage system with 12 cent coins, a greedy algorithm would not work. For instance, change for 15 cents would be a 12 cent coin and 3 pennies (4 coins total) whereas a dime and a nickel (2 coins) would be optimal.

In what types of coinage systems does the greedy algorithm not work?

$\endgroup$
7
  • $\begingroup$ Maybe a system where the values are relatively prime, plus some pennies? For example, if you have 1c, 3c and 4c (gcd(3,4) = 1) then the greedy algorithm for 6c would not work (4 + 1 + 1 is worse than 3 + 3). Or if you have 1c, 5c and 7c then it won't work for 10c (7 + 1 + 1 + 1 worse than 5 + 5). $\endgroup$
    – Sp3000
    Commented Feb 6, 2012 at 14:36
  • 1
    $\begingroup$ I suspect you need each coin to be at least twice the value of the next smaller coin. Certainly, it must be at least twice the value of the next smaller coin minus 1. $\endgroup$
    – Thomas Andrews
    Commented Feb 6, 2012 at 14:56
  • 7
    $\begingroup$ Here's a paper that summarizes some of what's known about this problem: A. Adamaszeka and M. Adamaszek, "Combinatorics of the change-making problem", European Journal of Combinatorics, Volume 31, Issue 1, January 2010, Pages 47–63. (dx.doi.org/10.1016/j.ejc.2009.05.002) $\endgroup$
    – PersonX
    Commented Feb 6, 2012 at 15:18
  • $\begingroup$ I haven't done much to verify this, but I think one notion would be that you don't want two coins of lesser value for which the sum of their values is greater than the value of the next coin. So in your example, you have the nickel, the dime, and the 12-cent piece, but the value of the nickel plus the value of the dime is greater than the value of the 12-cent piece. Notice that this never happens in the United States coinage system. $\endgroup$
    – Kurtis Zimmerman
    Commented Feb 6, 2012 at 15:23
  • 3
    $\begingroup$ @ChrisPhan, I think you should make that an answer, especially if you'd care to include one or two of the more useful results from that paper. $\endgroup$
    – Gerry Myerson
    Commented Feb 7, 2012 at 0:10

2 Answers 2

Reset to default
2
$\begingroup$

With thanks to Florian Ingels, here is a paper discussing this problem.

We can define a coinage system $C$ as being composed of an ascending series of coin denominations $\{c_i\}$ with $c_1=1$. If the greedy algorithm always works to deliver minimum number of any coins for every target value, it is canonical (in the paper's definition).

There are a number of useful rules of thumb that apply to most practically-encountered coinage systems.

Clearly any two-denomination system $\{1,c\}$ is canonical. Using as many high-denomination coins as possible gives the smallest coin count.

For a three denomination system $\{c_1=1,c_2,c_3\}$, any problem with the greedy algorithm has to occur between the two-coin solutions involving the biggest coin, $c_3+1$ and $c_3+c_2$. So if $c_2=2$ the greedy algorithm will always work.

We can separate the problem for a coinage system $C$ into distinct challenges if for a given denomination $c_k$ we have $c_k\mid c_j$ for all $j>k$; then the system is canonical if the two systems $C]_{c_k}=\{c_1,...,c_k\}$ and ${}_{c_k}[C = \{c_k/c_k=1, c_{k+1}/c_k,...,c_n/c_k\}$ are both canonical. So for the US coin system $U=\{1,5,10,25\}$ we can split into a cent-based coinage $U]_5 =\{1,5\}$ and a nickel-based coinage ${}_5[U = \{1,2,5\}$ both of which are canonical.

For the counterexample of $A=\{1,5,10,12,25\}$, no split is possible. The paper cited earlier gives that a non-canonical system will have some value that can be expressed in two coins that the greedy algorithm will use more coins for. Here as you identify, $5+10=15$ cents will have a wrong greedy solution of $12+1+1+1$.

$\endgroup$
1
  • $\begingroup$ Note that the two coins can be the same. For example 1+5+8 where greedy takes 8+1+1 instead of 5+5 $\endgroup$
    – gnasher729
    Commented Dec 7, 2023 at 15:01
-1
$\begingroup$

Intuitively, the requirement for the greedy algorithm to work for a coinset $c_1<c_2<...<c_n$ is that for any valid amount $v \in [c_i,c_{i+1}[$ the smallest solution for $v-c_i$ is smaller by 1 than the smallest solution for $v$.

EDIT: As Martin De la Fuente pointed out, the above is incorrect. Unfortunately the system won't allow me to delete the accepted answer.

$\endgroup$
2
  • $\begingroup$ Take $c_{1}=1$, $c_{2}=3$ and $c_{3}=4$. Your conditions mention are met, but the greedy algorithm won't work in this coinset $\endgroup$
    – Martín De la Fuente
    Commented Jun 4, 2020 at 14:50
  • $\begingroup$ @MartínDelaFuente you're right, I think I was thinking in log2 terms, but I don't remember. Have you studied the problem? Unfortunately it won't let me delete the answer $\endgroup$
    – mitchus
    Commented Jul 3, 2020 at 15:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .