Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a set of numbers, I'd like to split this set into 2 sets, where the sum of each set is as close to equal as possible. How would I go about doing this in a programmatic way?

Thanks in advance for any help!

EDIT: reworded for clarity perhaps?

"Given a set of integers, find a subset whose sum comes as close as possible to half the total of the entire set, without exceeding said total"

share|improve this question
5  
Have a look [here][1]. [1]: stackoverflow.com/questions/6597180/… –  Shai Covo Aug 2 '11 at 15:42
    
Thanks! That helps a lot –  alex heyd Aug 2 '11 at 15:47
    
@anon: That automatically happened after I tried to post it as an answer... –  Shai Covo Aug 2 '11 at 15:49
    
find the average, then go greedy –  yoyo Aug 2 '11 at 15:56
    
@Shai: Pressing the hyperlink button in the WYSIWYG editor for the answer box will automatically create a non-inline link. In comments, I think only inline links work, and the markup is [text](http://url). –  anon Aug 2 '11 at 15:57
show 1 more comment

1 Answer 1

http://en.wikipedia.org/wiki/Partition_problem

share|improve this answer
    
This refers to splitting into subsets that have exactly equal sums, not have sums as close as possible. –  Ross Millikan Aug 2 '11 at 20:05
    
@Ross, doesn't that mean that the question by the OP is more difficult than the Partition_problem? One assumes that there is a partition such that the sums are equal, while in the case of the OP, one needs to determine if that is true. –  picakhu Aug 2 '11 at 20:11
    
@picakhu: The true partition problem just has a yes/no answer: is there a perfect partition or not? In this problem, there is always an optimum answer, but you can't easily be sure you have it. The paper referenced in the reference of Shai Covo's comment says that if you have lots of numbers within a relatively small range there is almost always a solution with zero difference. –  Ross Millikan Aug 2 '11 at 20:15
    
The Karmarkar-Karp differencing algorithm will very often find a partition with sums very close to equal, but not necessarily optimal. In many applications this is good enough: the "as close as possible" need not be taken completely literally. –  Robert Israel Aug 3 '11 at 18:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.