Thread: Partitioning with Decimals

I have a list of numbers that represent bills due:

i.e.:

224.05
200.35
137.29
162.20
27.00

but a client might only send in a check for $388.34 and not say which invoices it is for.

Is there a way of determining which numbers in this list add up to 388.34?

This is a very simple example, the real list can be as long as 200 different invoice amounts.

I'm writing software so any programming classes or ideas you know that can help with this would be appreciated.

Thanks

I don't think that there is any efficient algorithm to determine which of the invoices the client desires to pay for; I would assume that the problem can't be solved in polynomial time. It is very similar to the subset sum problem, which is NP-complete, i.e. there is no known efficient way to calculate a solution for the problem (NP), and it is at least as hard to solve as the hardest problem for which a solution can be verified in polynomial time (NP-hard).

I would suggest that the client instead gets to choose which of the invoices to pay for.