我真的需要算法的高手在这里!所以,事情是我得到了例如像这样的数组:
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.