Как разделить список элементов на равные части в соответствии с их весом?

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!

11
задан Federico Cáceres 8 September 2010 в 21:02
поделиться