javascript - 如何将数组拆分为两个子集并使数组的子值之和尽可能相等

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 的整数

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

Answer 1

首先，正如已经确定的那样 - 问题是 NP-Hard ，具有分区问题的简化形式。

Reduction :
给定一个 partition problem 的实例，创建每个大小为 1 的列表。结果就是这个问题。

以上结论:
这个问题是NP-Hard的，没有已知的多项式解。

其次，由于问题的规模，任何指数和伪多项式的解决方案都将花费太长时间。

第三，它留给我们启发式和近似算法。

我建议采用以下方法:

1. 标准化子列表的比例，因此所有元素都将处于相同的比例(例如，所有元素都将标准化为 [-1,1] 范围，或者所有元素都将标准化为标准 normal distribution ).
2. 创建一个新列表，其中每个元素都是规范化列表中匹配子列表的总和。
3. 使用为子集和/分区问题开发的一些近似或启发式解决方案。

结果不会是最优的，但最优在这里确实是做不到的。