Calc Invoices to Pay?

[Ron Kracht]

Kenneth Brody wrote:
> Quoting Fairlight (Tue, 4 Mar 2008 10:47:54 -0500):
>
>   
>> The honourable and venerable Stanley Barnett spoke thus:
>>     
>>>> he's matching one sum against multiple cheques.
>>>>         
>>> No, I'm looking for "all the unpaid and posted invoices" whose totals
>>> adds up to the check payment amount.
>>>       
>> Yeah, but if you have a pool of 35 invoices that are unpaid and get a lump
>> sum payment of $1074.37, the way I understand it you're looking to
>> automatically find the combination of invoices that equals that amount and
>> flag them paid.
>>
>> Which is what I -meant- by one sum (the payment) against multiple cheques
>> (actually invoices, now that I reread).  But the permutation game is a
>> headache and 3/4.
>>     
>
> Oh, it can't be all that bad.  After all, if you have 35 invoices, there
> are only 34,359,738,367 possible combinations.  (Though you don't actually
> have to check all of them if you code it correctly.)
>
>   
What Mr. Barnett wants to do is known as the subset sum problem - see 
http://en.wikipedia.org/wiki/Subset_sum_problem

There are algorithms that will find combinations of values that total to 
a specified sum including one reasonably fast algorithm described in the 
wikipedia entry that is usable only if all values are non-negative - 
which is usually the case with invoices.

I'm not sure it's worth implementing a subset-sum algorithm for a one 
time problem but there are existing algorithms that apply to his problem 
and it's not entirely unreasonable to ask if someone has already 
implemented one of them.