# USA currency coins

## Homework Statement

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

## 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
51.1 KB · Views: 300
Last edited:

Ray Vickson
Homework Helper
Dearly Missed

## Homework Statement

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

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

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.