§ 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.