My own accounting python euler problem

Robert P. J. Day rpjday at
Sat Nov 7 22:47:36 CET 2009

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:

it's NP-complete.


Robert P. J. Day                               Waterloo, Ontario, CANADA

            Linux Consulting, Training and Kernel Pedantry.

Web page:                                

More information about the Python-list mailing list