0

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?

Bernard
  • 175,478
user1016724
  • 1

1 Answers1

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.

RobPratt
  • 45,619