We prove the algorithm always works by showing that the solution our greedy algorithm produces must be the same as the actual optimal solution. So we show that the number of dollars, quarters, dimes, nickels, and pennies that our greedy algorithm uses is the same as the number of each type of coin that the optimal solution would use.

We first show the pennies used by our greedy solution and the optimal solution are the same. Our greedy algorithm only uses pennies when the amount of change left to be given is less than 5 cents, so our solution uses 0, 1, 2, 3, or pennies. Now the optimal solution can only use 0, 1, 2, 3, or pennies as well, because it would not be optimal if it used 5 pennies. To be optimal, every 5 pennies would have to be replaced by a nickel, because that would use fewer coins. Note the sum of the value of the coins that are not pennies is a multiple of 5 in both solutions, so the total of the other coins in both cases ends in a 0 or 5. Thus, the number of pennies used by both solutions must be the same, because if that was not the case, then the total amount of change would be different between the two solutions.

Now we also know that the number of nickels in each solution must be 0 or 1, because the optimal solution would not have used two nickels instead of a dime (that would contradict optimal), and our greedy algorithm would not have either since it won't use nickels until there's less than 10 cents left to hand back.

Note that for both solutions, 0 <= the number of quarters <=3 because otherwise, the greedy algorithm would have used a dollar in place of 4 quarters and the optimal one would have too (otherwise it wouldn't be optimal). In fact, for the greedy algorithm, 0 <= the number of dimes <= 2 and 0 <= the number of nickels <= 1 for both algorithms as well because if there were more than 2 dimes, the greedy algorithm would have used another quarter, and if there were more than 1 nickels, the greedy algorithm would have used another dime. These bounds hold for the optimal algoithm as well, because it would never have 2 nickels instead of a dime and it would never have 3 dimes instead of a quarter and a nickel, because that would contradict it being optimal. Thus, for both solutions, there are at most 6 coins other than pennies and dollars. We know the number of pennies are the same, so there are two cases:

Case 1 - If the numbers of dollar coins for both solutions are the same, then both solutions have 6 or fewer coins that are dimes, nickels, and quarters and the sum of the values of those coins must be equal or else only 1 solution is correct (and we know our greedy solution is always correct if not optimal). If both solutions have the same coins, then both the greedy and optimal solutions use the same coins, so therefore, the greedy solution is optimal. If the amount of money from the coins is the same but the coins are different, then we need to show that any two sets of coins that add up to the same amount of money are such that the least number of coins would be chosen by both the optimal algorithm and the greedy algorithm. That will show that the greedy algorithm produces the optimal solution. So the sets of 6 or fewer coins are shown below, and the only cases where two sets of coins add up to the same amount of money are: n + d + d = 25, q = 25, q + q = 50, n + d + d + q = 50, n + d + d + q + q = 75, q + q + q = 75. In all of these cases, it is clear that the greedy algorithm would choose the fewer number of coins. It is also clear that the optimal solution would also contain the smaller number of coins by the definition of optimal. Thus, the greedy solution is the optimal one in this case.

• no coins = 0

• n = 5
• d = 10
• q = 25

• n + d = 15
• n + q = 30
• d + d = 20
• d + q = 35
• q + q = 50

• n + d + d = 25
• n + d + q = 40
• n + q + q = 55
• d + d + q = 45
• d + q + q = 60
• q + q + q = 75

• n + d + q + q = 65
• n + d + d + q = 50
• n + q + q + q = 80
• d + q + q + q = 85
• d + d + q + q = 70

• n + d + q + q + q = 90
• n + d + d + q + q = 75
• d + d + q + q + q = 95

• n + d + d + q + q + q = 100

symbol:frequency:code
a:0.0827128:1110
b:0.01558025:001101
c:0.02291213:00000
d:0.04903196:0001
e:0.1208615:011
f:0.02107916:110011
g:0.01993355:110010
h:0.06346661:1001
i:0.06804903:1011
j:0.00515523:11000011
k:0.00927941:001100
l:0.04903196:0010
m:0.02554703:00111
n:0.06346661:1010
o:0.07457899:1101
p:0.01672586:110001
q:0.00114561:1100001001
r:0.05327071:0100
s:0.06220644:1000
t:0.08901363:1111
u:0.02703632:01011
v:0.00801925:1100000
w:0.02646351:01010
x:0.00171841:110000101
y:0.02348494:00001
z:2.2912E-4:1100001000
ABL: 4.231298