Method needed for financial problem

[dosh]

New. So not sure if this is the right place. Hopefully someone can help.

The problem is -I have a list of figures of amounts. I receive a number of cheques (checks if from the US) which are the the total of some of the figures (whole amount) and no figure is used twice. How can I make it easy to figure out which amounts add up to which. Example the list is $5 (lets call it x1),$18(x2),$7(x3),$6(x4), $9(x5), $10(x6),$2(x7) - now I receive a cheque for $14 so that it is for x1,x3 and x7. The next is for $24 that is for x2 and x4. The last one is for x5 and x6.

So can any work out an equation to do this or a way to easily do this for me? as the number of figures can be in there 100's.

[jemidiah]

As I understand it, you have a total and want to partition it (that's the formal word, usually used in "integer partitions") using subtotals from a fixed list. There's a uniqueness problem. In your example, $24 = x2 + x4 = x1 + x5 + x6, since the latter totals $5+$9+$10 = $24 as well. It would be astonishing to me if the real list didn't suffer from the same problem. Maybe it suffers to a lesser extent, or cents are included which would at least make collisions "rarer".

Your question in general is probably NP(-complete?), so likely very difficult in general. If the number of subtotals is very low the problem can be efficiently brute forced. In your example, it's possible to just compute all 2-term, 3-term, etc. sums of subtotals and keep a lookup table. The brute force approach is polynomial in the number of terms in the subtotals, though, which would make it extremely impractical for hundreds of terms for a list of more than, say, 10 subtotals.

However, if there are only, say, 5 terms but hundreds of different subtotal amounts, brute force would be viable. To be specific, the 5-term with 100 subtotal choices case would require looking at (100 choose 5) = 100*99*98*97*96 / 5*4*3*2*1 = 75,287,520 totals, which a computer could easily keep track of. [n choose k is the usual "binomial coefficient"] From this calculation, though, you can see how many possible totals there are for a relatively small number of subtotals.


In all, I imagine your question doesn't have a practical and/or unique answer.

[jemidiah]

When I said "the brute force approach is polynomial in the number of terms in the subtotals", I meant the degree of the polynomial is the number of terms in the subtotals, for a fixed list of possible subtotal values. This differs from the usual usage of the phrase, which would have meant the degree is some fixed constant. (It's a minor point I'm reasonably sure nobody reading this will mind, but still.)