* FAQ    * Search  * Register * Login 
Active topics
Unanswered topics

All times are UTC-06:00



Post new topic  Reply to topic  [ 4 posts ] 
Author Message
 Post subject: Programmatic / mathematics problem
PostPosted: Thu Dec 10, 2009 1:25 am 
Offline
DBB Captain
DBB Captain
User avatar

Joined: Thu Nov 05, 1998 12:01 pm
Posts: 589
ICQ: 247668
Website: http://www.descentrangers.com/
WLM: verraneventide@hotmail.com
Yahoo Messenger: verraneventide
AOL: verraneventide
Location: Colorado
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?

_________________
.
http://www.descentrangers.com

http://soundcloud.com/verran


Top
   
 Post subject:
PostPosted: Thu Dec 10, 2009 2:46 am 
Offline
DBB Ghost Admin
DBB Ghost Admin
User avatar

Joined: Thu Nov 05, 1998 12:01 pm
Posts: 12133
Website: http://www.tomandcatherine.com
Location: I'm so glad to be home
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.


Top
   
 Post subject:
PostPosted: Thu Dec 10, 2009 9:31 am 
Offline
DBB Material Defender
DBB Material Defender
User avatar

Joined: Tue Nov 23, 2004 3:31 pm
Posts: 4900
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.


Top
   
 Post subject: Re: Programmatic / mathematics problem
PostPosted: Sat Jun 10, 2017 10:55 am 
Offline
DBB Ace
DBB Ace

Joined: Mon Apr 10, 2000 2:01 am
Posts: 245
Website: http://anarchyinteractive.com
Location: Lexington, KY
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.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 4 posts ] 

All times are UTC-06:00


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron



Descent'rs have piloted these pages
 
The layout and contents contained within this site are © DescentBB.net 1997-2006.
Descent, Descent II are © Parallax Software Corporation.
Descent III is Outrage Entertainment.
Descent is a Trademark of Interplay Productions.

Miner Wars™ is trademark of Keen Software House s. r. o.
.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group