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?

## Programmatic / mathematics problem

- Lothar
- DBB Ghost Admin
**Posts:**12133**Joined:**Thu Nov 05, 1998 12:01 pm**Location:**I'm so glad to be home-
**Contact:**

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.

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

- Foil
- DBB Material Defender
**Posts:**4900**Joined:**Tue Nov 23, 2004 3:31 pm**Location:**Denver, Colorado, USA

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.

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

### Re: Programmatic / mathematics problem

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.

There's just enough religion in the world to make men hate one another but not enough to make them love.