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

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