algorithm - 如何根据项目的重量将项目列表分成相等的分区？

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

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

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

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.

这种方法的运行时间是 O(n^2) 并且保证让你在精确解的 4/3 的因数内。

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