My own accounting python euler problem

[Robert P. J. Day]

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