Newsgroups: rec.puzzles
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 14 May 91 21:59:27 GMT
Subject: Re: Optimal change and related trivia

farrell@cs.uq.oz.au writes:

>There is an old problem about the most efficient way to give change in a cash
>transaction, i.e.  requiring the least coins.

And se...@Morgan.COM (Seth Breidbart) notes:

>The problem is NP-complete; it is trivial to reduce the knapsack
>problem to it.  (Throw in a lot of stamps of very tiny denomination,
>you lose iff you have to use some of them.)  Therefore, it's quite
>unlikely that anyone will find an efficient algorithm.

Knapsack is only weakly NP-complete, so there are algorithms that
operate in time polynomial in the amount to be changed.  For instance,
you can use dynamic programming: recursively find the optimum change
for each value less than the amount, then find the minimum, over
values one coin less than the amount, of the number of coins needed to
make change.  The best change uses one coin more than that minimum.

Dan