如何根据项目的权重将项目列表拆分为相等的分区？

Question

我有一个项目列表,有点像这样:

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

我想把这个列表分成......说两组,以便每组中项目的权重总和尽可能相等,即:

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

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

目前我正在通过以锯齿形的方式遍历有序列表来解决这个问题.在第一遍中将具有更多权重的项目分配给每个组,在第二遍中分配权重较小的项目,依此类推.

这样可行,但它有缺陷.我认为在我们之间交换项目的组的第二次传递将导致更均匀的分布式组,但所涉及的代码可能变得太复杂.

有人知道更有效或更聪明的方法吗？

谢谢!

Answer 1

这是分区问题的优化版本,它是NP完全的,尽管,根据那篇文章,"有许多启发式方法可以在很多情况下解决问题,无论是最佳还是近似."

该文章的方法部分包含许多方法来进行近似或伪多项式解.具体来说,如果你能得到一个近似的答案,你可以尝试贪婪的方法:

模仿儿童为游戏选择团队的方式的问题的一种方法是贪婪算法,该算法以降序顺序遍历数字,将每个数据分配给具有较小总和的任何子集.

这种方法的运行时间是O(n^2)并确保使您达到精确解决方案的4/3.

如果你必须有一个精确的解决方案并且你的数据集足够小,你总是可以采用蛮力的方法来产生每种可能性(这是指数级的O(2^n)).根据您的性能需求,这可能就足够了.