我需要一位算法专家来帮忙!问题是我有一个类似这样的数组:
[
[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的整数
我正在寻找一个“足够接近”的解决方案——它不必是精确的最优解。
O(n^2)
。(除非它可以是任何子集,而不是子数组-那么它就是分区问题,但是问题就会变得混乱) - amit[1048,893,160]
。我没有数学证明,但我的直觉是这将实现类似的结果。 - Felix Kling