小编典典

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

algorithm

我有一些像这样的物品清单:

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

目前,我正在通过以Z字形方式遍历有序列表来解决此问题。将第一遍的权重较高的项目分配给每个组,在第二遍的权重较低的项目进行辅助,依此类推。

可以,但是有缺陷。我在想,如果我在组之间进行第二次交换(在组之间交换项目),将导致组分布更加均匀,但是所涉及的代码可能会变得过于复杂。

有人知道这样做的更有效或更智能的方法吗?

谢谢!


阅读 299

收藏
2020-07-28

共1个答案

小编典典

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

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

模仿贪婪算法是解决问题的一种方法,该算法模仿孩子选择游戏团队的方式,该算法按降序遍历数字,将每个数字分配给总和较小的子集。

这种方法的运行时间O(n^2)可以确保达到精确解决方案的四分之三。

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

2020-07-28