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
that sounds like the classic knapsack problem: http://www.itl.nist.gov/div897/sqg/dads/HTML/knapsackProblem.html it's NP-complete. 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
