http://qs1969.pair.com?node_id=87702


in reply to Re^2: (Golf) Giving Change
in thread (Golf) Giving Change

With certain combinations of currency, the greedy strategy won't work so well. Imagine you need to give 30 cents change, using US coins but not nickels. The intuitively "correct" solution is three dimes, but the greedy strategy will give one quarter and five pennies. If you want to define the greedy answer to be the correct one, that's fine, but you didn't make that clear in the problem statement.

If the coins are a little stranger, the greedy strategy will fail altogether. Maybe the land of Frobozz has 2-frob and 3-frob coins, but no 1-frob coin. You can make 7 frobs with one 3 and two 2s, but if you start out by giving two 3s, you're stuck.

We could define a "generalized penny" to be a coin which every other coin is a multiple of. The penny and the yen are both "pennies" by this definition. If such a coin exists, the greedy method will always produce an answer. There's no frob-penny in my example, though.

Replies are listed 'Best First'.
Re^4: (Golf) Giving Change
by tadman (Prior) on Jun 12, 2001 at 05:26 UTC
    The explanation from the land of Frobozz certainly clears up what you were getting at. I would posit, though, that most countries, unlike Frobozz, have designed their currency structure along some sort of logic which would limit this possiblity.

    Humans regularily give change from a machine displaying only a single total, without benefit of a breakdown, moving from one bin to the next, trying to make a good total. There is little "wiggle room" in a fully stocked register. It is only when they start to run out of things that it gets interesting.

    I, for one, would not want to design a Frobozzian register which had to explain how to give change.

    The absence of a "penny" placeholder would cause a little havoc with change dispensing from a mechanical perspective, as you pointed out with your $0.30 example, which would be rendered impractical.
[reply]

In Section Meditations