1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: USA currency coins

  1. Apr 16, 2016 #1
    1. The problem statement, all variables and given/known data
    I can't understand why cashier's algorithm is optimal for U.S coins: 1, 5,10,25,100

    2. Relevant equations

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

    Attached Files:

    Last edited: Apr 16, 2016
  2. jcsd
  3. Apr 16, 2016 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Apr 16, 2016 #3
    I have attached a table that explains cashier algorithm. I would be glad if you orient me.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted