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

我这里真的需要一个算法大师！所以问题是我得到了一个像这样的数组：

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

我想把它分开，这样它看起来像这样：

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

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

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

Scales:

• 数组中约 1000 个元素（子列表）
• 元素是 10^9 以内的整数

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

首先，正如已经确定的那样 - 问题是NP-Hard http://en.wikipedia.org/wiki/NP-hard，具有分区问题的简化形式。

减少 http://en.wikipedia.org/wiki/Polynomial-time_reduction:
给定一个实例分区问题 http://en.wikipedia.org/wiki/Partition_problem，创建每个大小为 1 的列表。结果就是这个问题。

从上面得出的结论:
该问题是NP-Hard问题，并且没有已知的多项式解。

Second由于问题的规模，任何指数和伪多项式解决方案都将花费很长时间才能发挥作用。

Third,它给我们留下了启发式算法和近似算法。

我建议采用以下方法：

1. 标准化子列表的比例，因此所有元素都将具有相同的比例（也就是说，所有元素都将标准化为范围[-1,1]或者全部标准化为标准正态分布 http://en.wikipedia.org/wiki/Normal_distribution).
2. 创建一个新列表，其中每个元素将是规范化列表中匹配子列表的总和。
3. 使用为子集和/分区问题开发的一些近似或启发式解决方案。

结果不会是最优的，但最优在这里确实是遥不可及的。