0
$\begingroup$

I was thinking about how giving change is a greedy algorithm for the optimal result, where the optimal result is getting the lowest amount of bills and coins possible. The algorithm I am referring to is where you go from the largest denomination to the smallest, at each point saying "how many of X bills can I give?", subtracting from the total, and moving down to the next bill.

However, this does not guarantee the optimal solution always.

A simple, constructed example is if your denominations are $1$ cent penny, $\$1.50$ bill, and $\$ 2.00 $ bill. If you want to give $\$3$ change, this algorithm will make you end up getting a $\$ 2.00$ bill and $100$ pennies instead of $2$ $\$1.50$ bills.

So, my question is, what properties of denominations makes this greedy algorithm effective?

$\endgroup$
0
$\begingroup$

There is a lot of literature on this subject, giving complex criteria for when the greedy solution works. One easy criterion, assuming that your denominations are integers (e.g. in terms of pennies) and 1 is one of your denominations, and when you sort your denominations in increasing order each denomination is at least twice the previous denomination, then the greedy algorithm will give the optimal solution.

$\endgroup$
  • $\begingroup$ Interesting.. are there any more "natural" examples than mine for which the greedy algorithm doesn't work? Perhaps an actual national currency somewhere? $\endgroup$ – MCT Jun 24 '15 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.