
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
November 30th, 2008, 03:50 PM  #1 
Newbie Joined: Nov 2008 Posts: 2 Thanks: 0  Find Closest To Total Out Of A Set Of Values
Hello, First off, please forgive me if this is one of those obviousanswered type of things. I'm normally a computer programmer, and am out of my depth asking a question on a math forum. There's a little history of working with algorithms in my past, so I fully expect that there's a quick and dirty way of doing this that's named after a person. However, I actually have no idea what search criteria to look for, or even how to word my question, so I'll just describe what I'm trying to do, and hopefully someone has an idea where to point me. It goes like this: I'm working on a project whose function in part is to select a group of numbers from a set that has a total closest to (but not exceeding) a given value. An example would be the following: 1 3 5 7 9 11 13 15 17 19 < Find the values that total closest to 20 "Set Theory" seems to fit what I'm trying to do, since it's a set of numbers being operated on. Any help would be appreciated. As I said earlier, I'm a programmer, so if there's a link that shows an algorithm that can be done programmatically, then WOOHOO BONUS. But if it's strictly a math site, that's ok too. Thanks for reading, and take care, Michael Fritzius 
December 1st, 2008, 09:32 AM  #2 
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  Re: Find Closest To Total Out Of A Set Of Values
This is the subset sum problem. Or rather, the corresponding optimization problem. There isn't a "quick and dirty way of doing this that's named after a person" ( ) for this problem, as it is NP. However, there's a dynamic programming (i.e. ground up) solution that is polynomial in the size of the set. In other words, do a search for "dynamic programming subset sum". You'll probably need to make it store the "best solution so far", and return that, since the problem is generally states as "Is there a subset of X that sums to n?" Rather than "give the subset of X that is closest to n." If you need more information, let me know... 
December 1st, 2008, 05:44 PM  #3 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Find Closest To Total Out Of A Set Of Values
The algorithm to be used depends mainly on two things: * How many items can be expected? If 10 is a typical number, all combinations can be tested; if 100, that's impractical/impossible. * Is an exact answer required, or just a good guess? 
December 3rd, 2008, 03:49 AM  #4  
Newbie Joined: Nov 2008 Posts: 2 Thanks: 0  Re: Find Closest To Total Out Of A Set Of Values Quote:
Quote:
Thanks you two, and take care, Michael Fritzius  
December 3rd, 2008, 05:39 AM  #5 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Find Closest To Total Out Of A Set Of Values
So the lists may be large, and approximate solutions are allowed. That suggests a method like simulated annealing (although, to be fair, I see SA as the solution to most numerical problems like this...). Here's the first SA idea that comes to mind. Set initial temperature in the range 0 < t < 1, and choose an initial set. At each step, form a new set by discarding one member and adding 02 new members randomly. If the fitness of the new set is better than the old set, compare the new set's fitness to the record fitness; replace the record with the current set if it's an improvement. If the new set is an improvement on the old set (regardless of whether it's a record), replace the current set with the new set; otherwise, choose the new set with probability t. Decrease t slightly and repeat. Fitness function: Let x = the target minus the sum of the members of S. If x = 0, the fitness is 0 (the best possible). If x is positive, choose the element y not in the set closest to x. If the sum of (S union {y}) is greater than the target, return min(target  sum (S), sum (S union {y})  target); otherwise, return fitness(S union {y}). If x is negative, choose the element y in the set closest to x. If the sum of (S minus {y}) is less than the target, return min(sum (S)  target, target  sum (S minus {y})); otherwise, return fitness(S minus {y}). 

Tags 
closest, find, set, total, values 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Help!Find the total moment.  go2255  Linear Algebra  1  October 28th, 2013 09:43 AM 
Find the closest point  OriaG  Calculus  5  September 8th, 2012 03:36 PM 
Find the total capacitance  sivela  Physics  3  January 29th, 2012 12:06 PM 
find values of ? that correspond to the ? values?  space55  Calculus  0  October 10th, 2010 03:23 PM 
find the total area  zgonda  Algebra  2  August 18th, 2010 06:56 AM 