如何阵列分成两个子集,并保持阵列的子值总和尽可能相等阵列、子集、总和、两个

2023-09-11 04:05:48 作者:原来我三岁

我真的需要算法的高手在这里!所以,事情是我得到了例如像这样的数组:

I really need an master of algorithm here! So the thing is I got for example an array like this:

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

和我想将其分割,所以它看起来是这样的:

and I want to split it up, so that it looks like this:

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

所以现在,为什么我希望它太像这样?

so now, why do I want it too look like this?

由于我想保持子值的总和尽可能相等。因此, 970 870 + 110 78 23 + 50 。 因此,在这种情况下,它是很容易的,因为如果你只是分裂他们,只能看第一分度值,将已经是正确的,但我想同时检查并让他们尽可能相等,因此,它还将与合作其中有100个子阵的阵!因此,如果任何人都可以告诉我,我可以编程实现这样的算法,这将是非常巨大的!

Because I want to keep the sum of sub values as equal as possible. So 970 is about 870 + 110 and 78 is about 23 + 50. So in this case it's very easy because if you would just split them and only look at the first sub-value it will already be correct but I want to check both and keep them as equal as possible, so that it'll also work with an array which got 100 sub-arrays! So if anyone can tell me the algorithm with which I can program this it would be really great!

尺度:

〜1000元(子表)数组中 元素是整数可达10 ^ 9

我要寻找一个足够接近的解决方案。 - 它并不一定是确切的最佳解决方案

I am looking for a "close enough solution" - it does not have to be the exact optimal solution.

推荐答案

感谢所有的答案中,暴力破解攻击是一个好主意,NP难是关系到这一点,但事实证明,这是一个多背包问题,可以使用该PDF文档来解决。

Thanks for all the answers, the bruteforce attack was a good idea and NP-Hard is related to this too, but it turns out that this is a multiple knapsack problem and can be solved using this pdf document.

 
精彩推荐
图片推荐