On Sat, 7 Nov 2009, vsoler 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. > > My first question is: > 1. given a list of invoives I=[500, 400, 450, 200, 600, 700] and a > check Ch=600 > how can I print all the different combinations of invoices that the > check is possibly cancelling
by the way, there's a bit more to it than just seeing if you can match the cheque amount exactly. some python solutions are here: http://rosettacode.org/wiki/Knapsack_Problem and a general solution allows you to place different "values" on which items you pack into your knapsack. say a customer has outstanding invoices for 200, 400 and 600, and you get a cheque for 600. what do you apply that against? the single invoice for 600, or the two for 200 and 400? that depends. if all invoices have the same "value", it won't matter. but if the invoice for 600 just went out, while the two others are just about to become, say, overdue so that a penalty is about to be applied, your customer would probably *really* appreciate it if you applied that cheque to the older invoices. in general, then, you can not only see what matches exactly but, for the sake of your customer, you can give higher value to paying off older invoices. that's how the general knapsack problem works. rday -- ======================================================================== Robert P. J. Day Waterloo, Ontario, CANADA Linux Consulting, Training and Kernel Pedantry. Web page: http://crashcourse.ca Twitter: http://twitter.com/rpjday ======================================================================== -- http://mail.python.org/mailman/listinfo/python-list
