如何将数组拆分为两个子集，并使数组的子值总和尽可能相等
我真的需要一个算法大师！ 所以事情就是我得到了一个像这样的数组：
[ [870, 23] [970, 78] [110, 50] ] 我想将它拆分，所以它看起来像这样：
// first array [ [970, 78] ] // second array [ [870, 23] [110, 50] ]
所以现在，为什么我想要它看起来像这样？
因为我想保持子值的总和尽可能相等。 所以970约为870 + 110约为23 + 50 。 所以在这种情况下它很容易，因为如果你只是拆分它们而只看第一个子值它已经是正确的但我想检查它们并保持它们尽可能相等，这样它也可以使用一个有100个子arrays的数组！ 所以，如果有人能告诉我我可以编程的算法，那真的很棒！
秤：
- 数组中的~1000个元素（子列表）
- 元素是最多10 ^ 9的整数
我正在寻找一个“足够接近的解决方案” – 它不一定是最合适的解决方案。
首先，正如已经确定的那样 – 问题是NP-Hard ，减少forms的分区问题。
减少 ：
给定分区问题的实例，创建每个大小为1的列表。 结果将是这个问题。
从以上结论 ：
这个问题是NP-Hard，并且没有已知的多项式解。
其次 ，由于问题的严重性 ，任何指数和伪多项式解决方案都需要很长时间才能工作。
第三，它给我们留下了启发式和近似算法。
我建议采用以下方法：
- 规范化子列表的比例，因此所有元素将处于相同的比例（例如，所有元素将被标准化为范围
[-1,1]或者所有元素将被标准化为标准正态分布 ）。 - 创建一个新列表，其中每个元素将是规范化列表中匹配子列表的总和。
- 使用为子集求和/分区问题开发的一些近似或启发式解决方案。
结果不是最优的，但最优在这里真的无法解决。
从我从原始post的讨论中收集的内容来看，你不是在寻找单个分裂点，而是想要在两个集合中分配所有对，这样两个集合中的每个集合中的总和大致相等。
由于足够接近的解决方案是可以接受的，也许您可以尝试基于模拟退火的方法？ （见http://en.wikipedia.org/wiki/Simulated_annealing ）
简而言之，我们的想法是，您可以通过随机将每对配置为左侧或右侧设置来开始。 接下来，您可以通过任一方式生成新状态
- a）从左到右移动一组随机选择的对，
- b）从右到左移动随机选择的对，或
- c）两者兼顾。
接下来，确定此新状态是好于还是差于当前状态。 如果它更好，请使用它。 如果情况更糟，只有当它被接受概率函数接受时才接受它，这是一个最初允许使用更差状态的函数，但随着时间的推移（或“温度降低”，越来越少有利于它们） SA术语）。 经过大量的迭代（比如100.000），你应该有一个非常好的结果。
可选地，多次重新运行该算法，因为它可能卡在局部最优中（尽管接受概率函数试图对此进行反击）。
这种方法的优点是实现起来很简单，您可以自己决定希望它继续寻找更好的解决方案多久。
我假设我们只是在数组中间寻找一个位置，将其分成第一和第二部分。
似乎线性算法可以做到这一点。 在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]; } }
感谢所有答案，暴力攻击是一个好主意，NP-Hard也与此相关，但事实certificate这是一个多背包问题，可以使用这个pdf文档解决。