• Support PF! Buy your school textbooks, materials and every day products Here!

USA currency coins

  • #1

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

Last edited:

Answers and Replies

  • #2
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

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.
 
  • #3
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.
 

Related Threads on USA currency coins

  • Last Post
Replies
6
Views
8K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
24
Views
4K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
4
Views
8K
  • Last Post
Replies
15
Views
936
Top