Programmatic / mathematics problem

[Verran]

Okay, this is a real-life scenario for the software my team and I are developing at work. Nope, it's not a homework assignment.

Let's say I have a total: 21.30

I need to take the numbers out of this list:
10.03, 9.50, 7.10, 7.10, 7.10, 5.20, 4.11

To get to the closest number that matches the total (21.30).

For example:
10.03 + 9.50 = 19.53
7.10 + 7.10 + 7.10 = 21.30 (wins)

The total and the numbers in the list are always dynamic.

We have already thought of starting with the lowest number and looping through the calculations from lowest to highest, rotating the lowest number as we go, until we hit the closest possible match. This may work, but we think there has got to be a better solution.

Our lead developer has a BA in mathematics and he is scratching his head on this one.

Any ideas?

[Lothar]

This sounds like a variation of the Knapsack Problem, which is NP-Complete. You're not going to come up with an exact solution to the problem short of an exhaustive search, which can be extremely slow.

You may find the polynomial-time \"approximate\" solution of the Subset Sum Problem to be useful.

[Foil]

Depending on common properties within your data, it may be worth doing some testing with common data, to see if you can find some common patterns to make use of (e.g. if there are many multiples of the same number, like your example).

Other than that, I believe Lothar is correct. An NP-Complete problem isn't something to spend much time trying to optimize.

[psionik]

It seems like you need a function that creates a new list based on the amount of entries in the list given to it that contains the difference in absolute values between each entry in the initial list and the target entry, then a function that parses the new list list for the lowest value.