Coin Change

Goal: Make change with the smallest number of coins

Definition (Canonical coin system)

A coin system is canonical if the value of a coin can be composed of previous values

Cashier’s Algorithm

Algorithm: Start with the largest denominations and dispense as many of those that fit (Greedy Algorithms)

Note: Only optimal for canonical coin systems

Claim

If solution is optimal, then number of nickels + number of dimes $\le$ 2

Proof: Assume to the contrary that the solution is optimal but sum > 2 Number of nickels must be $\le$ 1 because 2 nickels would be better expressed as a dime

Case 1: The solution has no nickels. Then it has at least 3 dimes. But then replacing 3 dimes with 1 quarter and 1 nickels gives a more optimal solution, a contradiction.

Case 2: The solution has 1 nickel. So it also has at least 2 dimes. But then replace 1 nickel and 2 dimes with 1 quarter, same contradiction. $\square$

Theorem

The cashier’s algorithm is optimal for the U.S. coin system ($\{1,5,10,25,100\}$ )

Proof: Induction on the amount to be paid, $x$.

Base case: $x=1$

• The only optimal solution is to take 1 penny.
• That is the greedy option, so the cashiers algorithm is optimal.

Inductive Hypothesis:

• Assume that the cashier’s algorithm is optimal when $x\le i\ge 1$

Inductive Step: $x=i+1$

• Let $c_k$ be the largest coin such that $c_k\le x$
• The cashier’s algorithm will take $c_k$
• We will show that any optimal solution takes $c_k$
  • Assume some optimal solution for $x$ does not take $c_k$
  • This needs enough coins of type $c_1,\dots ,c_{k-1}$ to add up to $x$
  • No optimal solution can do this because $P\le 4$, $N\le 1$, $N+D\le 2$, $Q\le 3$
• Next, after taking $c_k$, we will make change for $x-c_k$
• Since $x-c_k\le i$, the IH says that the cashier’s algorithm is optimal
• Observe that $c_k$ + optimal solution for $x-c_k$ is optimal solution for $x$ $\square$

Dynamic Solution

• Dynamic Programming
• Also works with non canonical coin systems
• Similar to the knapsack problem except you’re trying to minimize the number of coins instead of maximize value