On Thu, Aug 02, 2001 at 06:39:01PM +0900, Steve Hill wrote:
> 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 understand it kinda/sorta but I am not good at explaining things. The
algorithm starts with zero and works its way up. Its counts all the ways to amek
change for 1c and then all the ways for 2c then 3c, 4c, 5c, and so on. It uses
previously calculated values to calculate new ones. So w[4,50] and w[4, 25] made
their contribution in calculating w[4,75].

Did I get that right?? 

One of the things that interests me is some of the similarities between my
solution and the one given by Niklas. Maybe I am not as dumb as I think I am.
One can hope :)

> 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.

Well it doesn't mean that there isn't a p time solution. It just means we get to
have lots of fun trying to find one.

Sincerly,
Chris Moline