Dividing n balls of different mass into 2 groups with the groups having a similar mass to one another

Question

If there are n balls, each with a different mass, how could you divide the balls into two groups, so that the sum of the mass in one group is as close as possible to the sum of the mass of the other group? Is it possible to calculate it in excel or some other program?

Answer 1

If the masses of the balls are $\ m_1, m_2, \dots, m_n\ $, and $\ M=\sum_\limits{i=1}^n m_i\ $, then your problem is equivalent to the following 0-1 knapsack problem: \begin{eqnarray} \text{Maximise} &\sum_{i=1}^n x_i m_i & \\ \text{subject to}&\sum_{i=1}^n x_i m_i &\le\frac{M}{2}\\ \text{and}\ \ & x_i\in\left\{0,1\right\}& \text{for}\ i=1,2,\dots,n\ . \end{eqnarray} The Wikipedia article linked to above lists some of the techniques available for solving the problem.