partition array into the three most homogeneous parted sum.

Question

Say we have an unordered array with 10 elements, like this: (in this case is ordered, but in fact, what is needed is the best solution)

• [6] => 19
• [5] => 18
• [8] => 18
• [1] => 18
• [2] => 16
• [4] => 15
• [9] => 11
• [0] => 10
• [3] => 8
• [7] => 6

Which is the best way, or how could I achieve divide it into 3 groups, so the sum of them are the most homogeneous manner. say for example 19+15+10=44, 18+18+8=44, 18+16+11+6=51 (note: i'm pretty sure this is not the best answer)

Is there a non-bruteforce way to achieve this partition? Could you lead me in the correct way to do it?

Answer 1

You can solve the problem via integer programming as follows. Let $I$ be the set of values, with frequencies $f_i$, and let $G$ be the set of groups. Define nonnegative integer variable $x_{i,g}$ to be the number of times value $i$ appears in group $g$. Let $t = (\sum_{i\in I} i \cdot f_i)/|G|$ be the target sum, and define nonnegative surplus variable $u_g$ and slack variable $v_g$ for group $g$. The problem is to minimize $\sum\limits_{g\in G} (u_g+v_g)$ subject to \begin{align} \sum_{g \in G} x_{i,g} &= f_i &&\text{for $i\in I$}\\ \sum_{i \in I} x_{i,g} - u_g + v_g &= t &&\text{for $g \in G$} \end{align} For the given example, $I=\{6,8,10,11,15,16,18,19\}$, $|G|=3$, $t=46+1/3$, and the optimal objective value is $4/3$, with optimal $x_{i,g}$:

   1 2 3 
 6 0 0 1
 8 0 0 1 
10 0 1 0 
11 1 0 0 
15 0 0 1 
16 1 0 0 
18 0 2 1 
19 1 0 0 

The resulting group sums are 46, 46, and 47.