12
$\begingroup$

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?

  • 0
    https://stackoverflow.com/q/6597180/39241182018-03-03

2 Answers 2

3

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

  • 2
    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.2011-08-03
-2
  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.