Niklas Frykholm <r2d2 / acc.umu.se> wrote in message news:<p9V97.11850$9i1.935979 / e420r-atl1.usenetserver.com>...

....
> Here is my variant. It does $100 in 2.5s, $1000 in 31.2 s and
> $10000 in 343s without any precomputation. (Time is approximately linear
> in the ammount.)
> 
> It is built on a recursive algorithm which can be found at
> http://www.telospub.com/journal/MIER/Piele/Vol6No1/Piele613.html
> 
> To run fast it uses a buffer to store the computed values and uses an
> iterative rather than recursive algorithm. To reduce the memory requirements
> and the garbage collection/thrashing, the buffer does not store all values,
> but only the last 10001 ones (fewer if we ask for change for a smaller
> ammount than $100).
> 

I've just looked at the original paper, and I am a little puzzled by
it. Perhaps someone could explain why it doesn't underestimate the
number of combinations possible - it does not seem to take into
account the fact that multiple coins of the same denomination can be
used. to use the notation that they do if W[4,100] is the number of
ways of spliiting 100c using the coins up to the 4th (a 25c piece),
then

W[4,100]=W[3,100]+W[4,75]

This does not seem to take into account the fact that you can use
multiple coins of the same denomination, i.e. where is the
contribution from w[4,50] and W[4,25]? Thus I believe that this
algorithm may underestimate the number of combinations of coins.

I have an algorithm that I am working on at the moment. However, I
believe that this algorithm provides an overestimate of the ways of
counting change.

To conclude, this is an instance of the knapsack problem, which is a
well known NP-complete problem. So I very much doubt that a quick
(i.e. P time) solution exists. But it would be interesting to see what
the cleanest, quickest and most accurate heuristic is.

Best regards

Steve