如何根据物品的重量将物品列表分成相等的分区？ [英] How to split a list of items into equal partitions according to the item's weight?

问题描述

我有一个类似这样的项目列表：

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?

谢谢！

推荐答案

这是分区问题的优化版本，即NP-完整，但是，根据该文章，在许多情况下，都有启发式方法可以最佳或近似地解决问题。

This is the optimization version of the partition problem, which is NP-complete, although, according to that article, "there are heuristics that solve the problem in many instances, either optimally or approximately."

方法一节包含了多种近似或伪多项式解的方法。具体来说，如果您可以得到一个近似的答案，则可以尝试贪婪的方法：

The methods section of that article contains a number of ways to do approximate or pseudo-polynomial solutions. Specifically, if you can live with an approximate answer, you could try the greedy approach:

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

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），可以保证使您到达准确解决方案的四分之三。

The running time of this approach is O(n^2) and is guaranteed to get you to within a factor of 4/3 of the exact solution.

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

If you must have an exact solution and your data set is small enough, you could always take a brute force approach of generating every possibility (this is exponential, O(2^n)). Depending on your performance needs, this might be sufficient.

这篇关于如何根据物品的重量将物品列表分成相等的分区？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！