I just started greedy algorithms and I'm having some issues.
I looked at:
https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/04GreedyAlgorithmsI-2×2.pdf
the proof is in slides 5-6. The algorithm is straightforward and the properties are clear, but I don't understand the induction in slide 6:
Theorem. Cashier's algorithm is optimal for U.S. coins: 1, 5, 10, 25,
100. Pf. [by induction on x]
- Consider optimal way to change ck ≤ x < ck+1 : greedy takes coin k.
- We claim that any optimal solution must also take coin k.
- if not, it needs enough coins of type c1, …, ck–1 to add up to x
- table below indicates no optimal solution can do this
- Problem reduces to coin-changing x – ck cents, which, by induction, is optimally solved by cashier's algorithm
I know induction as in base case, induction hypothesis, and the induction step, but it seems like it is missing here.
My question:
What is the induction hypothesis and induction step here? Why is this proof valid?
Best Answer
Base case: $k=1$. Suppose that you want to change a value $x$ between $c_1=1$ (inclusive) and $c_2=5$ (not inclusive), i.e. $1\le x<5$. Then, the greedy will take a coin of $k=1$ and will set $x \leftarrow x-1$. That the greedy solves here optimally is more or less trivial.
Induction hypothesis: $k$. The greedy solves optimally for any value of $x$ such that $c_{k-1}\le x<c_k$.
Induction step: $k+1$. Show that the greedy solves optimally for any value of $x$ such that $c_k\le x<c_{k+1}$. Then, they use this table that you mention to show that this problem reduces to solving for $x\leftarrow x-c_k$ for which $0\le x-c_k<c_{k+1}-c_k$, which has been treated in the induction hypothesis.
Note that the table - which is the main part of the proof - can be constructed only for specific values of the coins. It does not hold for any possible choice of coin denominations, as they show in their next slide.