如何根据物品的重量将物品列表分成相等的分区？

我有一个有点像这样的项目列表：

[
  ["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

目前我正在通过以之字形方式遍历有序列表来解决这个问题。在第一遍中将权重较大的项目分配给每个组，在第二遍中将权重较小的项目分配给每个组，依此类推。

这工作正常，但它有缺陷。我认为，对在其中交换项目的组进行第二次传递将导致更均匀分布的组，但所涉及的代码可能会变得过于复杂。

有人知道更有效或更智能的方法吗？

Thanks!

这是优化版本分区问题，这是 NP 完全的，尽管根据那篇文章，“在许多情况下，有一些启发式方法可以最优或近似地解决问题。”

The methods该文章的部分包含许多进行近似或伪多项式解决方案的方法。具体来说，如果您可以接受近似答案，您可以尝试贪婪方法：

解决这个问题的一种方法是模仿孩子们选择游戏队伍的方式，即贪心算法，该算法按降序排列数字，将每个数字分配给总和较小的子集。

该方法的运行时间为O(n^2)并且保证您能得到精确解的 4/3 范围内的结果。

如果您必须有一个精确的解决方案并且您的数据集足够小，那么您始终可以采用强力方法来生成每种可能性（这是指数级的，O(2^n)）。根据您的性能需求，这可能就足够了。