DescentBB http://descentbb.net/ 

Programmatic / mathematics problem http://descentbb.net/viewtopic.php?f=7&t=16295 
Page 1 of 1 
Author:  Verran [ Thu Dec 10, 2009 1:25 am ] 
Post subject:  Programmatic / mathematics problem 
Okay, this is a reallife 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? 
Author:  Lothar [ Thu Dec 10, 2009 2:46 am ] 
Post subject:  
This sounds like a variation of the Knapsack Problem, which is NPComplete. 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 polynomialtime \"approximate\" solution of the Subset Sum Problem to be useful. 
Author:  Foil [ Thu Dec 10, 2009 9:31 am ] 
Post subject:  
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 NPComplete problem isn't something to spend much time trying to optimize. 
Author:  psionik [ Sat Jun 10, 2017 10:55 am ] 
Post subject:  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. 
Page 1 of 1  All times are UTC06:00 
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ 