in reply to (Golf) Giving Change
 Is the set of denominations guaranteed to contain a penny? If not, this is the knapsack problem (which is NPcomplete, BTW).
 Is 2,250 pennies a valid solution for $22.50?
Re: Re: (Golf) Giving Change
by ZZamboni (Curate) on Jun 12, 2001 at 04:23 UTC

No, it does not correspond to the 01 Knapsack problem
(which is NPcomplete), but to the
fractional
knapsack problem, which can be solved using a greedy algorithm
(put as many of the largest denomination as will fit, then continue
to the next lower denomination, and so on until you reach the
target amount).
ZZamboni
 [reply] 

 [reply] 
Re^2: (Golf) Giving Change
by tadman (Prior) on Jun 12, 2001 at 05:00 UTC

 The demoninations are not guaranteed to contain a penny,
as this might be for Japanese Yen, which do not use fractional
currency (smallest unit is 1 Yen). Fortunately, you are not
required to give "change" for these trifling units smaller
than the smallest "coin" or "bill".
 2,250 may add up to $22.50, but it is not a valid
solution. You would get this if you fed the currency into the
function backwards, though. As ZZamboni points out,
proceed in order from largest to smallest and all will be well.
 [reply] 

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 2frob and 3frob coins, but no 1frob 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 frobpenny in my example, though.
 [reply] 

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] 

