Slashdot Mirror
Making Change
Roland Piquepaille writes "There are mostly four kinds of coins in circulation in the U.S: 1 cent, 5 cents, 10 cents, and 25 cents. But is it the most efficient way to give back change? This Science News article says that a computer scientist has found an answer. "For the current four-denomination system, [Jeffrey Shallit of the University of Waterloo] found that, on average, a change-maker must return 4.70 coins with every transaction. He discovered two sets of four denominations that minimize the transaction cost. The combination of 1 cent, 5 cents, 18 cents, and 25 cents requires only 3.89 coins in change per transaction, as does the combination of 1 cent, 5 cents, 18 cents, and 29 cents." He also found that change could be done more efficiently in Canada with the introduction of an 83-cent coin and in Europe with the addition of a 1.33- or 1.37-Euro coin. Check this column for more details and references." The paper (postscript) is online.
Do what Australia did a while back and round everything to the nearest 5c and get rid of 1c and 2c coins entirely (so now Australian coins are 5c, 10c, 20c, 50c, $1 and $2). I couldn't decide whether I liked it to start with, but after a little while you realise just how much shrapnel you carry around and have no intention of using except to empty it from your pocket/wallet at the end of every day. Every time I go to another country and have to again deal with 1/2 cent/euro cent/pence/etc I just appreciate this move even more.
"Because it's there." - George Mallory, when asked why he wanted to climb Mt Everest, March 18, 1923 (New York Times)
In France (and probably other countries) most of the prices end in .00 and the taxes are already included (unlike Canada where I live). It's much simpler that way. If only there was a way to convince stores to do that in here...
Opus: the Swiss army knife of audio codec
If only there was a way to convince stores to do that in here...
Its not up to the store, but the law. You must show the PST and GST on every sale in Canada. There was some debate a couple years ago about changing it to hidden costs, but that seems to have been quelled with recent wars and weed laws.
sin(6cos(r)+5A)
The logic for determining change is really easy for a cashier. start with the largest coin and work your way down until it all adds up.
I can't think of an example where that doesn't work in a 1,5,10,25 system, but it is definitely not a valid rule in general. For example in a 1,40,41 system you can give 80 cents change with two coins, but your method would use fourty coins.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
Engineers also speak PDE, only in a different dialect.
> In Canada, it's illegal to pay for any good or service, with more than 25 of any given denomination.
What he's talking about can be found in Section 8 of the Currency Act.
Basically it is a no-nuisance law to stop people from doing things like pay fines using pennies. It doesn't say the money can be confiscated...
Many businesses will still except coins if they have been rolled. I know I have paid for movie tickes and extra value meals with rolls of nickles and dimes.
From the statute:
(2) A payment in coins referred to in subsection (1) is a legal tender for no more than the following amounts for the following denominations of coins:
-
Rod (Canadian)
Some egghead thinks "optimal" means "fewest coins returned in change, on average."
/. to come along and rip everything out of context.
No no no. Academia don't have to think about definitions. We just define it that way.
Be seriously, RTFA, people. The important part of this result is not that 18 or 83 cent recommendations. The author did it in jest in reference to the phrase "What this country needs is a good five cent cigar". (cited in the footnote of the paper). Just wait for
The important part of this paper is the second half, the general analysis of methods for finding "optimal" denominations or "optimal" change returns (the first defined to minimize the number of coins returned on average, the second defined as given a set denomination, finding the best way to represent a given amount). It gives asymtotic results. It is more of a computer science excercise then anything else.
W
Engineers also speak PDE, only in a different dialect.
I can't think of an example where that doesn't work in a 1,5,10,25 system
The reason you can't think of any examples in the 1,5,10,25 system is because 10 and 25 are both multiples of five. Therefore whatever you could make with a 25, you could also make with five 5s. So if you would ever have five 5s or two 5s, just use a 25 or a 10, respectively. In 1,40,41 system, 41 is not a multiple of 40 (or vice versa), so it makes finding the optimal number of coins a bit more difficult, since you have to find the optimal number of factors for your change given the different coins. In a 1,5,10,25 system, 5 is already a factor of the other important coins, so you can just count up how many 5s you'd need and then reduce that into 25s and 10s. (Of course the mind usually does it the other way round.)
--
Promoting critical thinking since 1994.
Don't you think that the addition of sales tax already solves this problem?
On untaxed items (e.g. Groceries here in New York State) your explanation makes sense, but on most items we pay a sales tax somewhere between 4 and 9 percent, depending on the county and item. It almost always requires change.
Further, if your explanation were the correct one, then gasoline would not be priced such that it is always something and 9 mils (e.g. $1.529).
www.wavefront-av.com
Cecil has the right answer instead of this complete conjecture.
I'm really sorry to say that your last sentence exactly encapsulates the US buying experience :-(. For your hypothetical $3.99 item, the price can be $4.19 (5% tax rate), $4.21 (5.5% tax rate), or ghod knows what -- sales tax in the US ranges from 0% to 8-9%, and sometimes you have state and local tax. It's really a P.I.T.A. (pain in the ass).
In Australia copper coins (1c & 2c) were taken out of circulation in 1991 (I think). So everything is rounded to a multiple of 5c. The rules for the rounding (set out by law) are:
For cash transactions:
1 & 2 cents -- rounded DOWN to the nearest 10 cents
3 & 4 cents -- rounded UP to the nearest 5 cents
6 & 7 cents -- rounded DOWN to the nearest 5 cents
8 & 9 cents -- rounded UP to the nearest 10 cents
Rounding is on the total value of the bill. Individual items should never be rounded.
And where a consumer pays by cheque, credit card or EFTPOS (electronic transaction) there is no need to round at all.
So basically you win some and you lose some, but it evens out in the end. If you're really diligent, yes you can use it to your advantage, but most people have a life instead.
"Because it's there." - George Mallory, when asked why he wanted to climb Mt Everest, March 18, 1923 (New York Times)
with denominations that do not divide evenly into each other it is non-trivial to find the optimal change for a given transaction.
..., c_k$, such that $\Sigma_{i=0}^k = n$ where $n$ is the amount of money in cents to change. Assume that we remove the coin with the largest value. The remaining coins, $c_2, ..., c_k$, represent the solution to the sub problem of changing $(n - c_1)$. If $c_2, ..., c_k$ is not optimal there exists another set of coins for this subproblem, $x_2, ..., x_k$, such that this solution has fewer coins. However this is a contradiction because we can now form a solution for the original problem, $n$, by combining $c_1$ with $x_2, ..., x_k$ that has a smaller size than the original optimal problem. This is a contradiction and hence $c_2, ..., c_k$ is an optimal answer to the subproblem and therefore the coin changing problem exhibits optimal substructure.
..., C(n-d_k)\}$.
whereas with the US denomination (and most denominations are designed for this reason) you can use a greedy algorithm to give back change (always choose the largest coin possible, repeat) and you are guaranteed to be giving back the fewest coins.
you can prove that a greedy algorithm provides an optimal solution if the problem has optimal substructure and the greedy choice property.
To prove optimal substructure consider a collection of coins for an optimal solution, $c_1,
To prove the greedy choice property we must show that a globally optimal solution can be arrived at by making a locally optimal, this is, greedy, choice.
For this particular set of American denominations we can prove the greedy property with a proof by contradiction. If the greedy choice were not optimal there would be an optimal collection such that:
1. some set of dimes, nickels, pennies added to more than 25 cents or
2. some set of nickels, pennies added to more than 10 cents or
3. some set of pennies added to more than 5 cents
However, all of these situations are impossible. If some set of pennies add to more than 5 cents, simply replace 5 pennies with a nickel (the greedy algorithm is better). If some set of nickel and pennies add to more than 10 cents and if there are two nickels, replace them with a dime; If there are a nickel and the rest pennies,
replace a nickel and 5 pennies with a dime. The same holds for a quarter. If three dimes, replace it with a quarter and a nickel. If it's two dimes and nickel/pennies, replace it with a quarter. And so on... The property of the coins that results in the greedy property is that each coin denomination divides evenly into the next larger coin denomination. Therefore each larger coin denomination that is removed must be replaced by at least two additional coins.
With non-even denominations you are required to actually search an n^2 space for the correct set of denominations. in fact, the algorithm is:
$C(n) = 1 + min \{C(n-d_1), C(n-d_2),
Additionally, $C(n) = 0$ for $n = 0$. We can ignore $n 0$ are we just define $C(n 0) = \infty$. By building the array in time/size $\Theta(nk)$, and keeping track at each step which value of was chosen for the minimum, then we can list the coins by tracing backwards through these recorded values. This augmentation takes no additional time since it can be done during building the array in time $\Theta(1)$.
So, basically you've changed the problem from a linear time algorithm in the amount of change to a quadratic time algorithm in the amount of change...
GOOD LUCK WALMART EMPLOYEES!
Almost. The piece of eight (the Spanish Milled Dollar, worth eight reales) was one of the principal coins of the colonies, but the coin was not broken up. Instead, coins of values equivalent to one-half, one-quarter, and one-eighth of a dollar. One piece of eight was worth on real, eight reales to a dollar...
And now you know.
You can never go home again... but I guess you can shop there.
The tellers come up with the most creative combinations that minimize my number of coins (and maximize theirs - this is in both of our interest).
Just as a note here, its probably not in their best interest to get back as many coins as possible.
I used to admin at a bank, and you are charged for "coin." This means the more you bring in which is unsorted, the more you are charged.
Of course, if they roll their coin then this is not a problem.
However, it would cost them more if they try to maximize their coin input without rolling.
Also, this is probably the most nit-picky post in my history of posting. God help us all.
"I'm not impatient. I just hate waiting." - My Dad
Eliminating the penny just makes sense.
Regarding the ancient, mystic aspect of your post, I think I can explain the history behind this some. In the old hebrew counting system, the leters were used for numbers (but it was decimal, it's just that they used letters instead of the current notation), and the letters for 18 spelled out the word for life. Hence, 18 was (and still is by some people) considered lucky.
There's no sig like SIGSEG