§ Greedy Coin change: proof by probing

§ Probing the coin set {1, 5, 10, 20, 100}

• Let O* be optimal solution for this coin set. I'll write copies x [coinval$] notationally.
• O* will convert 5x[1$] → 1x[5$] , because it's better to use less coins.
• O* will convert 2x[5$] → 1x[10$]
• O* will convert 2x[10$] → 1x[20$]
• O* will convert 5x[20$] → 1x[100$]
• So we summarize: O* can have at most: 4x[1$], 1x[5$], 1x[10$], 4x[20$]. If it has more than these, it can convert to one copy of a larger coin, losing optimality.

§ Optimal takes as many 100$ as greedy.

• Recall: G (the greedy solution) takes as many 100, 10, 5, 1 as possible, starting from 100, working its way down to 1.
• Let G[100$] be the number of copies of the 100$ coin the greedy solution uses to represent n.
• Claim: O[100$] >= G[100$]. Since O is optimal, it won't take more than greedy since that's wasteful, so as a Corollary O[100$] = G[100$].
• Suppose for contradiction that O[100$] < G[100$]. Then there is a 100$ to be made up by O, which G fulfils by using a [100$] coin.
• We know by probing that if we stick to coins less than [100$], O can have at most 4x[20$] + 1x[10$] + 1x[5$] + 4x[1$] coins.
• See that we can't add any more of [1$], [5$], [10$], [20$]. For example, suppose we try and use another [1$] coin. This means we have 4x[20$] + 1x[10$] + 1x[5$] + 5x[1$]. From probing, we know we should change 5x[1$] → 1x[5$]. This changes the sum to 4x[20$] + 1x[10$] + 2x[5$]. From probing, we know 2x[5$] → 1x[10$]. The sum becomes 4x[20$] + 2x[10$]. Again from probing, we know to be optimal and use less coins, we should change 2x[10$] → 1x[20$]. This makes the sum 5x[20$]. This too should be changed to 1x[100$], a fact we learnt from probing. But this contradicts the assumption that we want to use only coins smaller than [100$]. So if we are using coins smaller than [100$], the maximum value we can represent is given by 4x[20$] + 1x[10$] + 1x[5$] + 4x[1$] .
• The maximum value 4x[20$] + 1x[10$] + 1x[5$] + 4x[1$] adds up to 99$, which is one shy of 100$. So, it is impossible for us to represent a value of a 100 dollars using coins of value less than [100$] in an optimal fashion . Thus, O[100$] = G[100$], as it is best to take as many coins as possible.
• Repeat the argument for smaller denominations.