Programmatic / mathematics problem

For all coding issues - MODers and programmers, HTML and more.

Moderators: Jeff250, fliptw

Post Reply
User avatar
Verran
DBB Captain
DBB Captain
Posts: 589
Joined: Thu Nov 05, 1998 12:01 pm
Location: Colorado
Contact:

Programmatic / mathematics problem

Post by 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?
User avatar
Lothar
DBB Ghost Admin
DBB Ghost Admin
Posts: 12133
Joined: Thu Nov 05, 1998 12:01 pm
Location: I'm so glad to be home
Contact:

Post by 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.
User avatar
Foil
DBB Material Defender
DBB Material Defender
Posts: 4900
Joined: Tue Nov 23, 2004 3:31 pm
Location: Denver, Colorado, USA
Contact:

Post by 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
DBB Ace
DBB Ace
Posts: 245
Joined: Mon Apr 10, 2000 2:01 am
Location: Lexington, KY
Contact:

Re: Programmatic / mathematics problem

Post by 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.
There's just enough religion in the world to make men hate one another but not enough to make them love.
Post Reply