How to split a list of items into equal partitions according to the item's weight?

Question

Hi, I have a list of items that is somewhat like this:

[
  ["orange", 9],
  ["watermelon", 3],
  ["grapefruit", 6],
  ["peach", 8],
  ["durian", 2],
  ["apricot", 6]
]

I would like to split this list into... say two groups so that the sum of the weights of the items in each group are as equal as possible, i.e.:

List 1:
  orange: 9
  durian: 2
  apricot: 6
  TOTAL: 17

List 2:
  watermelon: 3
  grapefruit: 6
  peach: 8
  TOTAL: 17

Currently I'm solving this by traversing the ordered list in a zigzag'esque way. Assigning the items with more weight in the first pass to each group, assiging the items with less weight on the second pass, and so on.

This works ok, but it has it flaws. I'm thinking that a second pass on the groups in which I exchange items between them would result in more equally distributed groups, but the code involved could become too complicated.

Does someone know of a more efficient or intelligent way to do this?

Thanks!

Answer 1

You could total all the weights, divide by the number of groups, come up with a target weight, and then iterate through the items in descending weight order tossing them into the same group if they fit at or under the target weight, and into the other group if they don't.

There's probably some math dr.s out there who can come up with a formal proof of how best to do it, but that was my thought off the top of my head.

Answer 2

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.