How to split a list of items into equal partitions according to the item's weight?
This is the optimization version of the partition problem, which is NP-complete, although, according to that article, "there are heuristics that solve the problem in many instances, either optimally or approximately."
The methods section of that article contains a number of ways to do approximate or pseudo-polynomial solutions. Specifically, if you can live with an approximate answer, you could try the greedy approach:
One approach to the problem, imitating the way children choose teams for a game, is the greedy algorithm, which goes through the numbers in descending order, assigning each of them to whichever subset has the smaller sum.
The running time of this approach is O(n^2)
and is guaranteed to get you to within a factor of 4/3 of the exact solution.
If you must have an exact solution and your data set is small enough, you could always take a brute force approach of generating every possibility (this is exponential, O(2^n)
). Depending on your performance needs, this might be sufficient.