如何将一个数组分成两个子集，并尽可能保持子集的和相等

Question

我需要一位算法专家来帮忙！问题是我有一个类似这样的数组：

[
    [870, 23]
    [970, 78]
    [110, 50]
]

我希望将其拆分，使其看起来像这样：

// first array
[
    [970, 78]
]
// second array
[
    [870, 23]
    [110, 50]
]

那么现在，为什么我希望它看起来像这样呢？

因为我想尽可能保持子值的总和相等。所以，970 大约是 870 + 110，78 大约是 23 + 50。 所以在这种情况下很容易，因为如果你只是分割它们并且只看第一个子值，它就已经是正确的了，但我想检查两个并尽可能保持它们相等，这样它也可以用于有100个子数组的数组！所以，如果有人能告诉我用哪种算法可以编程实现这一点，那就太好了！

规模：

• 数组中有大约1000个元素（子列表）
• 元素是不超过10^9的整数

我正在寻找一个“足够接近”的解决方案——它不必是精确的最优解。

- noob

---

可能是重复的问题：如何将一个数组最优地分成两个子数组，使得两个子数组中元素的和相等。否则会出现错误。原文链接 - Felix Kling

@FelixKling 不是重复问题，他想要根据一个总和将一个数组分成两个子数组，而不是两个总和，实际上还有很多类似的问题。 - noob

@FelixKling 是的，没错，但不仅仅是有点难，而是非常难以解决。 - noob

@FelixKling 这不是分区问题，其他答案也是错误的。分区问题是当你需要从数组中取一个子集时，这里你只需要选择“分区点”- 你取一个子数组，而不是一个子集。暴力解决方案是通过检查每个可能的“分区”点和检查总和来实现O(n^2)。(除非它可以是任何子集，而不是子数组-那么它就是分区问题，但是问题就会变得混乱) - amit

例如，为什么不对每个子数组进行求和，然后针对该求和进行优化，即对于 [1048，893，160]。我没有数学证明，但我的直觉是这将实现类似的结果。 - Felix Kling

Answer 1

首先，正如已经确定的那样 - 问题是 NP-Hard，通过Partition Problem的减少形式得到。 减少： 给定一个partition problem实例，创建大小为1的列表。结果将完全是这个问题。

由上述可知：这个问题是NP-Hard的，没有已知的多项式解决方案。

第二，任何指数和伪多项式解决方案都需要太长时间才能工作，因为问题的规模太大。

第三，我们只能使用启发式算法和近似算法。

我建议采用以下方法：

1. 将子列表的比例标准化，使所有元素都处于相同的比例尺上（例如，全部标准化为范围为[-1,1]或全部标准化为标准正态分布）。
2. 创建一个新列表，在其中每个元素将是标准化列表中匹配子列表的总和。
3. 使用一些近似或启发式解决方案，该方案已针对子集和/分区问题进行了开发。

结果不会是最优的，但在这里真正的最优解是无法实现的。

- amit

Answer 2

根据原帖下的讨论，我了解到您不是在寻找单个分割点，而是想把所有的一对数分配到两个集合中，使得这两个集合中的数的和大致相等。

既然接受足够接近的解决方案，也许您可以尝试基于模拟退火的方法？ （见http://en.wikipedia.org/wiki/Simulated_annealing）

简而言之，思路是随机将每一对数分配到左侧或右侧集合中。接下来，通过以下方式生成新状态：

• a）将从左侧随机选择的一对数移动到右侧集合中，
• b）将从右侧随机选择的一对数移动到左侧集合中，或者
• c）同时执行a)和b)。

接下来，判断这个新状态是比当前状态更好还是更差。如果它更好，就使用它。 如果它更差，只有在被“接受概率函数”接受的情况下才采用该状态，“接受概率函数”是一个函数， 最初允许使用更劣的状态，但随着时间的推移（或者在SA术语中温度降低），越来越不赞成使用这些状态。 进行大量迭代（比如10万次）之后，你应该得到一个相当不错的结果。

可选地，多次重新运行此算法，因为它可能会陷入局部最优解（尽管接受概率函数试图抵消这种情况）。

这种方法的优点是实现简单，而且你可以自己决定要搜索更好解决方案的时间长度。

- Leon Bouquiet

Answer 3

我假设我们只是在数组中间寻找一个位置，将其分成第一部分和第二部分。

似乎可以使用线性算法来实现。以下是JavaScript代码示例：

arrayLength = 2;
tolerance = 10;

// Initialize the two sums.
firstSum = [];
secondSum = [];
for (j = 0; j < arrayLength; j++)
{
   firstSum[j] = 0;
   secondSum[j] = 0;
   for (i = 0; i < arrays.length; i++)
   {
      secondSum += arrays[i][j];
   }
}

// Try splitting at every place in "arrays".
// Try to get the sums as close as possible.
for (i = 0; i < arrays.length; i++)
{
   goodEnough = true;
   for (j = 0; j < arrayLength; j++)
   {
      if (Math.abs(firstSum[j] - secondSum[j]) > tolerance)
         goodEnough = false;
   }

   if (goodEnough)
   {
      alert("split before index " + i);
      break;
   }

   // Update the sums for the new position.
   for (j = 0; j < arrayLength; j++)
   {
      firstSum[j] += arrays[i][j];
      secondSum[j] -= arrays[i][j];
   }
}

- Hew Wolff

---

示例显示了从数组中间形成array1的元素，以及其余部分形成array2。因此不是在一个地方进行拆分。 - James

Answer 4

感谢所有的回答，暴力攻击是个好主意，NP-Hard也与此有关，但事实证明这是一个多重背包问题，可以使用this pdf document来解决。

- noob