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.

The are included when the recursion is applied to w[4,75]

	w[4,75] = w[3,75] + w[4,25]

The formula is a bit tricky to understand. I think the simplest way
is to look at it like this: If you shall give me 30c using 1c-, 5c-
and 10c-coins there are exactly two possibilities. Either you give me
30c using only 1c- and 5c-coins. Or you give me a 10c coin and the
remaining 20c using 1c-, 5c- and 10c-coins. They are mutually 
exclusive and you must do the one or the other.

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

But I have given you a P-solution in my post. Thus we conclude that
P=NP :)

No, not really. The general knapsack-problem is NP-complete but there
are instances that are not NP-complete. For example, if the sum is
bounded, if the size of knapscack and the knapsack items are bounded,
if the knapsack is superincreasing, etc.

// Niklas

A good way of getting out of boring assignments:

Boss:	I need you to write a Visual Basic program that ties
	togheter our accounting system with the customer database.

You:	But that is an NP-complete problem.

Boss:	Are you sure?

You:	Last time I checked.