16-1 Coin changing

Consider the problem of making change for $n$ cents using the fewest number of coins. Assume that each coin's value is an integer.

a. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution.

b. Suppose that the available coins are in the denominations that are powers of $c$, i.e., the denominations are $c^0, c^1, \ldots, c^k$ for some integers $c > 1$ and $k \ge 1$. Show that the greedy algorithm always yields an optimal solution.

c. Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution for every value of $n$.

d. Give an $O(nk)$-time algorithm that makes change for any set of $k$ different coin denominations, assuming that one of the coins is a penny.

Before we go into the various parts of this problem, let us first prove once and for all that the coin-changing problem has optimal substructure.

Suppose we have an optimal solution for a problem of making change for $n$ cents, and we know that this optimal solution uses a coin whose value is $c$ cents; let this optimal solution use $k$ coins. We claim that this optimal solution for the problem of $n$ cents must contain within it an optimal solution for the problem of $n - c$ cents. We use the usual cut-and-paste argument. Clearly, there are $k - 1$ coins in the solution to the $n - c$ cents problem used within our optimal solution to the $n$ cents problem. If we had a solution to the $n - c$ cents problem that used fewer than $k - 1$ coins, then we could use this solution to produce a solution to the $n$ cents problem that uses fewer than $k$ coins, which contradicts the optimality of our solution.

a. A greedy algorithm to make change using quarters, dimes, nickels, and pennies works as follows:

  • Give $q = \lfloor n / 25 \rfloor$ quarters. That leaves $n_q = n \mod 25$ cents to make change.
  • Then give $d = \lfloor n_q / 10 \rfloor$ dimes. That leaves $n_d = n_q \mod 10$ cents to make change.
  • Then give $k = \lfloor n_d / 5 \rfloor$ nickels. That leaves $n_k = n_d \mod 5$ cents to make change.
  • Finally, give $p = n_k$ pennies.

An equivalent formulation is the following. The problem we wish to solve is making change for $n$ cents. If $n = 0$, the optimal solution is to give no coins. If $n > 0$, determine the largest coin whose value is less than or equal to $n$. Let this coin have value $c$. Give one such coin, and then recursively solve the subproblem of making change for $n - c$ cents.

To prove that this algorithm yields an optimal solution, we first need to show that the greedy-choice property holds, that is, that some optimal solution to making change for $n$ cents includes one coin of value $c$, where $c$ is the largest coin value such that $c \le n$. Consider some optimal solution. If this optimal solution includes a coin of value $c$, then we are done. Otherwise, this optimal solution does not include a coin of value $c$. We have four cases to consider:

  • If $1 \le n < 5$, then $c = 1$. A solution may consist only of pennies, and so it must contain the greedy choice.
  • If $5 \le n < 10$, then $c = 5$. By supposition, this optimal solution does not contain a nickel, and so it consists of only pennies. Replace five pennies by one nickel to give a solution with four fewer coins.
  • If $10 \le n < 25$, then $c = 10$. By supposition, this optimal solution does not contain a dime, and so it contains only nickels and pennies. Some subset of the nickels and pennies in this solution adds up to $10$ cents, and so we can replace these nickels and pennies by a dime to give a solution with (between $1$ and $9$) fewer coins.
  • If $25 \le n$, then $c = 25$. By supposition, this optimal solution does not contain a quarter, and so it contains only dimes, nickels, and pennies. If it contains three dimes, we can replace these three dimes by a quarter and a nickel, giving a solution with one fewer coin. If it contains at most two dimes, then some subset of the dimes, nickels, and pennies adds up to $25$ cents, and so we can replace these coins by one quarter to give a solution with fewer coins.

Thus, we have shown that there is always an optimal solution that includes the greedy choice, and that we can combine the greedy choice with an optimal solution to the remaining subproblem to produce an optimal solution to our original problem. Therefore, the greedy algorithm produces an optimal solution.

For the algorithm that chooses one coin at a time and then recurses on subproblems, the running time is $\Theta(k)$, where $k$ is the number of coins used in an optimal solution. Since $k \le n$, the running time is $O(n)$. For our first description of the algorithm, we perform a constant number of calculations (since there are only $4$ coin types), and the running time is $O(1)$.

b. When the coin denominations are $c^0, c^1, \ldots, c^k$, the greedy algorithm to make change for $n$ cents works by finding the denomination $c^j$ such that $j = \max \{0 \le i \le k: c^i \le n\}$, giving one coin of denomination $c^j$, and recursing on the subproblem of making change for $n - c^j$ cents. (An equivalent, but more efficient, algorithm is to give $\lfloor n / c^k \rfloor$ coins of denomination $c^k$ and $\lfloor (n \mod c^{i + 1}) / c^i \rfloor$ coins of denomination $c^i$ for $i = 0, 1, \ldots, k - 1$.)

To show that the greedy algorithm produces an optimal solution, we start by proving the following lemma:

Lemma

For $i = 0, 1, \ldots, k$, let $a_i$ be the number of coins of denomination $c^i$ used in an optimal solution to the problem of making change for $n$ cents. Then for $i = 0, 1, \ldots, k - 1$, we have $a_i < c$.

Proof

If $a_i \ge c$ for some $0 \le i < k$, then we can improve the solution by using one more coin of denomination $c^{i + 1}$ and $c$ fewer coins of denomination $c^i$. The amount for which we make change remains the same, but we use $c - 1 > 0$ fewer coins.

To show that the greedy solution is optimal, we show that any non-greedy solution is not optimal. As above, let $j = \max\{0 \le i \le k: c^i \le n\}$, so that the greedy solution uses at least one coin of denomination $c^j$. Consider a nongreedy solution, which must use no coins of denomination $c^j$ or higher. Let the non-greedy solution use $a_i$ coins of denomination $c^i$, for $i = 0, 1, \ldots, j - 1$; thus we have $\sum_{i = 0}^{j - 1} a_i c^i = n$. Since $n \ge c^j$, we have that $\sum_{i = 0}^{j - 1} a_i c^i \ge c^j$.. Now suppose that the non-greedy solution is optimal. By the above lemma, $a_i \le c - 1$ for $i = 0, 1, \ldots, j - 1$. Thus,

$$ \begin{aligned} \sum_{i = 0}^{j - 1} a_i c^i & \le \sum_{i = 0}^{j - 1} (c - 1) c^i \\ & = (c - 1) \sum_{i = 0}^{j - 1} c^i \\ & = (c - 1) \frac{c^j - 1}{c - 1} \\ & = c^j - 1 \\ & < c^j, \end{aligned} $$

which contradicts our earlier assertion that $\sum_{i = 0}^{j - 1} a_i c^i \ge c^j$. We conclude that the non-greedy solution is not optimal.

Since any algorithm that does not produce the greedy solution fails to be optimal, only the greedy algorithm produces the optimal solution.

The problem did not ask for the running time, but for the more efficient greedy algorithm formulation, it is easy to see that the running time is $O(k)$, since we have to perform at most $k$ each of the division, floor, and mod operations.

c. With actual U.S. coins, we can use coins of denomination $1$, $10$, and $25$. When $n = 30$ cents, the greedy solution gives one quarter and five pennies, for a total of six coins. The non-greedy solution of three dimes is better.

The smallest integer numbers we can use are $1$, $3$, and $4$. When $n = 6$ cents, the greedy solution gives one $4$-cent coin and two $1$-cent coins, for a total of three coins. The non-greedy solution of two $3$-cent coins is better.

d. Since we have optimal substructure, dynamic programming might apply. And indeed it does.

Let us define $c[j]$ to be the minimum number of coins we need to make change for $j$ cents. Let the coin denominations be $d_1, d_2, \ldots, d_k$. Since one of the coins is a penny, there is a way to make change for any amount $j \ge 1$.

Because of the optimal substructure, if we knew that an optimal solution for the problem of making change for $j$ cents used a coin of denomination $d_i$, we would have $c[j] = 1 + c[j - d_i]$. As base cases, we have that $c[j] = 0$ for all $j \le 0$.

To develop a recursive formulation, we have to check all denominations, giving

$$ c[j] = \begin{cases} 0 & \text{if $j \le 0$}, \\ 1 + \min\limits_{1 \le i \le k} \{c[j - d_i]\} & \text{if $j > 1$}. \end{cases} $$

We can compute the $c[j]$ values in order of increasing $j$ by using a table. The following procedure does so, producing a table $c[1..n]$. It avoids even examining $c[j]$ for $j \le 0$ by ensuring that $j \ge d_i$ before looking up $c[j - d_i]$. The procedure also produces a table $denom[1..n]$, where $denom[j]$ is the denomination of a coin used in an optimal solution to the problem of making change for $j$ cents.

1
2
3
4
5
6
7
8
9
COMPUTE-CHANGE(n, d, k)
    let c[1..n] and denom[1..n] be new arrays
    for j = 1 to n
        c[j] = 
        for i = 1 to k
            if j  d[i] and 1 + c[j - d[i]] < c[j]
                c[j] = 1 + c[j - d[i]]
                denom[j] = d[i]
    return c and denom

This procedure obviously runs in $O(nk)$ time.

We use the following procedure to output the coins used in the optimal solution computed by $\text{COMPUTE-CHANGE}$:

1
2
3
4
GIVE-CHANGE(j, denom)
    if j > 0
        give one coin of denomination denom[j]
        GIVE-CHANGE(j - denom[j], denom)

The initial call is $\text{GIVE-CHANGE}(n, denom)$. Since the value of the first parameter decreases in each recursive call, this procedure runs in $O(n)$ time.