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

  • Thread starter Thread starter Sebastian Martinez
  • Start date Start date
  • Tags Tags
    Usa
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
2 replies · 2K views
Sebastian Martinez
Messages
11
Reaction score
0

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
 

Attachments

  • Screenshot (24).png
    Screenshot (24).png
    34.8 KB · Views: 435
Last edited:
Physics news on Phys.org
Sebastian Martinez said:

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.
 
Ray Vickson said:
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.