Given a finite set $P = \{ p_1, \dots, p_n \} $ of integers, I'd like to split it into two subsets $A = \{ a_1, \dots, a_m \} \subseteq P$ and $B = \{ b_1, \dots, b_r \} \subseteq P$, where $m + r = n$, and, for each subset, the sum of the numbers is as close as possible to half the total of the sum of the numbers in $P$. More precisely, we have the following constraints $$\sum_i^m a_i \leq \left \lceil \frac{\sum_j^n p_j}{2} \right \rceil $$ and $$\sum_i^r b_i \leq \left \lceil \frac{\sum_j^n p_j}{2} \right \rceil $$ and $$\sum_i^m a_i + \sum_i^r b_i \leq \sum_j^n p_j $$

How would I go about doing this in a programmatic way?



  • 1
    $\begingroup$ This refers to splitting into subsets that have exactly equal sums, not have sums as close as possible. $\endgroup$ – Ross Millikan Aug 2 '11 at 20:05
  • $\begingroup$ @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. $\endgroup$ – picakhu Aug 2 '11 at 20:11
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Aug 2 '11 at 20:15
  • 2
    $\begingroup$ 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. $\endgroup$ – Robert Israel Aug 3 '11 at 18:54
  1. Sort your set DESC, like if you've [1,3,2,5,6], after DESC sort it will look like this: [6,5,3,2,1].
  2. Now you'll have 'SET1' and 'SET2' as your sub sets.
  3. if (SET1<=SET2){The element in the given set should come into the 'SET1';} else{The element in the given set should come into the 'SET2';}
  4. And of-course you'll eliminate the element you enter into the subsets 'SET1' OR 'SET2' from the given super set.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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