[ruby-talk:19065] Re: Who can count change??

Niklas Frykholm <[e-mail]> wrote in message news:<Mrda7.16965$[e-mail]>...
> 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.

Niklas,
thank you. Your explanation is considerably better than the one in the
original article :-)

I agree that there are certain bounded cases of knapsack which are
P-time. I'm wondering whether your solution is really a P-time
solution, or whether that depends on the relation of the buffer size
to the amount you are trying to count - your solution effectively
trades space for time by holding a buffer of previously computed
amounts.

The solution I was contemplating was to find the minimum coin split of
the amount. e.g. 12c =1*10c +2*1c and then calculate the decomposition
of each of those. You need to calculate a table of the no of ways for
each coin (which uses this method). However, the problem with the
method is it can't cope with possible interaactions between coins of
diffent types. e.g. 15c =10c*1 +5c *1, so assuming coin types are
independent=W[10c]*W[5c]. However, a 10c piece has a minimum coin
decomposition of 5c *2. The algorithm copes with multiple coins of the
same type, and will correctly gain the no of different decompositions
of 5c*2, but can't cope with the fact that 15c is better described as
5c*3, and overestimates the number of combinations as a result.

Anyway, I may not have time to post a full solution - got to integrate
the accounts database with the customer database (and in VB not ruby,
ick!) :-)

Best regards

Steve