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

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 也与此相关，但事实证明这是一个多背包问题，可以使用此 pdf 文档来解决。