Load balancing: how to split a set of numbers into two parts with approximately equal sums?

Question

Algorithms

At the input we have a set D of N numbers. It is required to optimally split it into two so that the sums of the numbers in the resulting sets are approximately equal:

D(N) ==> D1(N1) и D2(N2), причём ABS(SUM(D1)-SUM(D2))=MIN, N1+N2=N, SUM(D1)+SUM(D2)=SUM(D)

I made the simplest implementation through random and a large number of iterations, but I would like to write a clear and fast algorithm (I understand that stability is not guaranteed in the general case). Please tell me which way to dig? At least keywords for googling (I suspect that this is from the field of clustering algorithms). An algorithm for partitioning into an arbitrary number of parts M (M is less than N) would also be interesting.

Answer 1

For splitting into two groups, the problem is reduced to the problem of a knapsack with the weight of the knapsack equal to half the total weight of the stones and the value of the stones equal to their weight.

Answer 2

As already mentioned, this problem reduces to the knapsack problem. Since you need speed, I suggest using a greedy algorithm, something like this:
1. Sort the sequence in ascending order
2. Calculate the sum of the sequence
3. Take the maximum possible number of elements from the beginning of the list so that their sum does not exceed the sum of the list divided by the number of parts.
4. Repeat, excluding the selected elements from the list, and reducing the number of parts by one.