MHB Problem of making change for n cents

[evinda]

Hello! (Wave)

I am looking at the following exercise.

Consider the problem of making change for $n$ cents using the fewest number of
coins. Assume that each coin’s value is an integer.
Describe a greedy algorithm to make change consisting of quarters, dimes,
nickels, and pennies. Prove that your algorithm yields an optimal solution.Could you give me a hint what we could do? (Thinking)

 

[phymat]

Hello! (Wave)

I am looking at the following exercise.

Consider the problem of making change for $n$ cents using the fewest number of
coins. Assume that each coin’s value is an integer.
Describe a greedy algorithm to make change consisting of quarters, dimes,
nickels, and pennies. Prove that your algorithm yields an optimal solution.Could you give me a hint what we could do? (Thinking)

The algorithm works by choosing the coin with the highest value, subtract that value from the amount to change, and repeat until the amount to change is 0. To prove this greedy algorithm yields an optimal solution, we must show optimal substructure and the greedy choice property. Optimal substructure:
Assume to make changes for n cents, the first coin chosen by the greedy algorithm is a c1 coin with value of n1. Let C be the optimal solution to change n cents. Then C – {c1} is an optimal solution to change n-n1 cents. Otherwise, let the optimal solution be B. Then B U{c1} contains fewer coins than C and yet both makes up n cents, so C cannot be the optimal solution making change for n cents, which is a contradiction. Greedy choice property:
If our first choice is a penny, then the amount to change is at most 4 cents. Optimal choice cannot make the change without using a penny, since any other coin makes too much change. If our first choice is a nickel, then the amount to change is between 5 cents and 9 cents. If the optimal choice uses at least 5 pennies, we can turn it to a nickel and use fewer coins, contracting that it is an optimal solution. Otherwise, the optimal choice can only change 4 cents, not enough to make the change. If our first choice is a dime, then the amount to change is between 10 cents and 24 cents. If the optimal choice uses at least 5 pennies, we can turn it to a nickel and use fewer coins. Otherwise, if it uses 2 nickels, we can turn it to a dime. Otherwise, it can only make change for at most 9 cents, not enough to make the change. If our first choice is a quarter, then the amount to change is at least 25 cents. If the optimal choice uses at least 5 pennies, we can turn it to a nickel and use fewer coins. Otherwise, if the optimal solution uses at most 2 dimes, it must use enough pennies to make up at least 25 cents, and we can turn it to a quarter and use fewer coins. Otherwise, the optimal solution uses at least 3 dimes, we can turn it to a quarter and a nickel and use fewer coins.
Therefore the greedy choice property is satisfied.

 

[evinda]

The algorithm works by choosing the coin with the highest value, subtract that value from the amount to change, and repeat until the amount to change is 0. To prove this greedy algorithm yields an optimal solution, we must show optimal substructure and the greedy choice property. Optimal substructure:
Assume to make changes for n cents, the first coin chosen by the greedy algorithm is a c1 coin with value of n1. Let C be the optimal solution to change n cents. Then C – {c1} is an optimal solution to change n-n1 cents. Otherwise, let the optimal solution be B. Then B U{c1} contains fewer coins than C and yet both makes up n cents, so C cannot be the optimal solution making change for n cents, which is a contradiction.

I see... (Nod)

Greedy choice property:
If our first choice is a penny, then the amount to change is at most 4 cents. Optimal choice cannot make the change without using a penny, since any other coin makes too much change. If our first choice is a nickel, then the amount to change is between 5 cents and 9 cents. If the optimal choice uses at least 5 pennies, we can turn it to a nickel and use fewer coins, contracting that it is an optimal solution. Otherwise, the optimal choice can only change 4 cents, not enough to make the change. If our first choice is a dime, then the amount to change is between 10 cents and 24 cents. If the optimal choice uses at least 5 pennies, we can turn it to a nickel and use fewer coins. Otherwise, if it uses 2 nickels, we can turn it to a dime. Otherwise, it can only make change for at most 9 cents, not enough to make the change. If our first choice is a quarter, then the amount to change is at least 25 cents. If the optimal choice uses at least 5 pennies, we can turn it to a nickel and use fewer coins. Otherwise, if the optimal solution uses at most 2 dimes, it must use enough pennies to make up at least 25 cents, and we can turn it to a quarter and use fewer coins. Otherwise, the optimal solution uses at least 3 dimes, we can turn it to a quarter and a nickel and use fewer coins.
Therefore the greedy choice property is satisfied.

Could you explain to me what we are supposed to show?
Why do we say how high the amount to change is, based on out first choise?