Optimizing U.S. Coin Values for Cashier's Algorithm

[Sebastian Martinez]

Homework Statement

I can't understand why cashier's algorithm is optimal for U.S coins: 1, 5,10,25,100

Homework Equations

The Attempt at a Solution

The way cashier's algorithm works is that you pick the denomination of closest value to the expected amount. I am trying to read a lot of slides but it's not clear. One key point to understand is that each denomination is a multiple of the previous denomination, but what does that tell me about its optimality?... I am trying to understand the attached table

 

[Ray Vickson]

Homework Statement

I can't understand why cashier's algorithm is optimal for U.S coins: 1, 5,10,25,100

Homework Equations

The Attempt at a Solution

The way cashier's algorithm works is that you pick the denomination of closest value to the expected amount. I am trying to read a lot of slides but it's not clear. One key point to understand is that each denomination is a multiple of the previous denomination, but what does that tell me about its optimality?

Sufficient conditions for optimality of the "greedy algorithm" (which is the formal name given to the algorithm you describe) can be found in the paper
http://www.cs.yorku.ca/~andy/courses/3101/lecture-notes/CoinChange.pdf . The U.S. (and Canadian) coin denominations satisfy those conditions, so you can be sure that the "usual" way of making change results in the smallest number of coins, for any change amount. Of course, counterexamples exist for other denomination sets, so you cannot use the usual method to make change optimally in every country.

Google "coin-changing problem" for lots of related material.

 

[Sebastian Martinez]

Sufficient conditions for optimality of the "greedy algorithm" (which is the formal name given to the algorithm you describe) can be found in the paper
http://www.cs.yorku.ca/~andy/courses/3101/lecture-notes/CoinChange.pdf . The U.S. (and Canadian) coin denominations satisfy those conditions, so you can be sure that the "usual" way of making change results in the smallest number of coins, for any change amount. Of course, counterexamples exist for other denomination sets, so you cannot use the usual method to make change optimally in every country.

Google "coin-changing problem" for lots of related material.

I have attached a table that explains cashier algorithm. I would be glad if you orient me.