My Math Forum Find Closest To Total Out Of A Set Of Values

 Applied Math Applied Math Forum

 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 obvious-answered 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:
 Originally Posted by CRGreathouse 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?
Any number of items can be expected. No idea how big the array would be any given time. If it helps, I could sort the array in some fashion before running an algorithm against it so it's not so random. And an exact value isn't required since that might be imposible for any given set, just close enough or a best guess.

Quote:
 Originally Posted by cknapp 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...
I will check this out. Been busy the past couple days so I haven't had time. I did do a search and it looks like this might work, but without digging into it for awhile, it's hard to understand.

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 0-2 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post go2255 Linear Algebra 1 October 28th, 2013 09:43 AM OriaG Calculus 5 September 8th, 2012 03:36 PM sivela Physics 3 January 29th, 2012 12:06 PM space55 Calculus 0 October 10th, 2010 03:23 PM zgonda Algebra 2 August 18th, 2010 06:56 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top