On Nov 8, 8:39 am, vsoler <vicente.so...@gmail.com> wrote: > In the accounting department I am working for we are from time to time > confronted to the following problem: > > A customer sends us a check for a given amount, but without specifying > what invoices it cancels. It is up to us to find out which ones the > payment corresponds to. > > For example, say that the customer has the following outstanding > invoices: $300, $200, $50; and say that the check is for $250. This > time it is clear, the customer is paying bills $200 and $50. > > However, let's now say that the outstanding invoices are $300, $200, > $100 and that the check is for $300. In this case there are already > two possibilities. The customer is paying the $300 invoice or the $200 > and $100. In other words, there is more than one solution to the > problem.
The problems that you mention are only a SUBSET of the total problem. Example: oustanding invoices are for 300, 200, and 100 and the cheque is for 450 -- in general the total of the cheque amounts does not equal the total of any possible selection of outstanding invoice amounts. I would be very surprised if a real accounting department did not already have a set of business rules for dealing with a problem that has existed since invoices and cheques were invented. I would be extremely surprised if a real accounting department could be persuaded to imagine a subset of their unpaid/underpaid/overpaid invoice problem as being an instance of the (extended) knapsack problem :-) -- http://mail.python.org/mailman/listinfo/python-list
