My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
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 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
code_monkey is offline  
 
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...
cknapp is offline  
December 1st, 2008, 05:44 PM   #3
Global Moderator
 
CRGreathouse's Avatar
 
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?
CRGreathouse is offline  
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
code_monkey is offline  
December 3rd, 2008, 05:39 AM   #5
Global Moderator
 
CRGreathouse's Avatar
 
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}).
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2019 My Math Forum. All rights reserved.