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.

a. Always give the highest denomination coin that you can without going over, that is, $\lfloor n / C \rfloor$ coins of the largest denomination $C \le n$. Then, repeat this process on the remaining $n \bmod C$ cents until it drops to $0$.

Let $a, b, c, d$ be the numbers of quarters, dimes, nickels, and pennies in an optimal solution. Each of the following would contradict optimality:

  • $d \ge 5$: $5$ pennies can be replaced by $1$ nickel, saving $4$ coins.
  • $c \ge 2$: $2$ nickels can be replaced by $1$ dime, saving $1$ coin.
  • $b \ge 3$: $3$ dimes can be replaced by $1$ quarter and $1$ nickel, saving $1$ coin.
  • $b = 2$ and $c = 1$: $2$ dimes and $1$ nickel can be replaced by $1$ quarter, saving $2$ coins.

Hence, in an optimal solution,

  • pennies make up $d \le 4 < 5$ cents,
  • nickels and pennies make up $5c + d \le 5 + 4 = 9 < 10$ cents, and
  • dimes, nickels, and pennies make up $10b + 5c + d \le \max(2 \cdot 10 + 4, 10 + 5 + 4) = 24 < 25$ cents.

Since dimes, nickels, and pennies make up less than $25$ cents, $n - 25a < 25$, so $a = \lfloor n / 25 \rfloor$, which is the greedy choice. Let $n_1 = n - 25a$. Since nickels and pennies make up less than $10$ cents, $b = \lfloor n_1 / 10 \rfloor$. Let $n_2 = n_1 - 10b$. Since pennies make up less than $5$ cents, $c = \lfloor n_2 / 5 \rfloor$, and finally $d = n_2 - 5c$. Every count in the optimal solution is exactly the one the greedy algorithm picks, so the greedy solution is optimal.

b. Given an optimal solution $(x_0, x_1, \dots, x_k)$ where $x_i$ indicates the number of coins of denomination $c_i$ . We will first show that we must have $x_i < c$ for every $i < k$. Suppose that we had some $x_i \ge c$, then, we could decrease $x_i$ by $c$ and increase $x_{i + 1}$ by $1$. This collection of coins has the same value and has $c − 1$ fewer coins, so the original solution must of been non-optimal. This configuration of coins is exactly the same as you would get if you kept greedily picking the largest coin possible. This is because to get a total value of $V$, you would pick $x_k = \lfloor V c^{−k} \rfloor$ and for $i < k$, $x_i\lfloor (V\mod c^{i + 1})c^{-i} \rfloor$. This is the only solution that satisfies the property that there aren't more than $c$ of any but the largest denomination because the coin amounts are a base $c$ representation of $V\mod c^k$.

c. Let the coin denominations be $\{1, 3, 4\}$, and the value to make change for be $6$. The greedy solution would result in the collection of coins $\{1, 1, 4\}$ but the optimal solution would be $\{3, 3\}$.

d. See algorithm $\text{MAKE-CHANGE}(S, v)$ which does a dynamic programming solution. Since the first forloop runs $n$ times, and the inner for loop runs $k$ times, and the later while loop runs at most $n$ times, the total running time is $O(nk)$.