将数组拆分为权重相似的子数组

Question

我有一个n正数的数组。我需要将其拆分为N连续的子数组;n > N.

我需要尽量减少[max S(j) over j] - [min S(j) over j]， 其中S(j)表示子数组j-th元素的总和，(j = 1,...,N)。

即，所有子数组都应该有"相同"的元素总和。

我相信这个问题是已知的。有人可以指出我的算法、实现或出版物吗？

Answer 1

这个问题相当于找到max S(j) over all j的最小值。

直觉：

• 假设所有可能max S(j) over all j的最小值为xmax，因此结果将是xmax - xmin。

• 假设，另一个可以为我们提供更好结果的ymax > xmax，这意味着ymax - ymin<xmax - xmin_x002D_=">ymin > xmin->min S(j) - ymax>min S(j) - xmax，这不应该发生。

因此，问题指向找到最小值max S(j) over all j

这可以通过使用二叉搜索来解决。 假设整个数组的总和是X，所以我们有了我们的算法：

int start = 0;
int end = X;
int result = 0;
while(start <= end){
int mid = (start + end)/2;
for(int i = 0; i < n; i++){
if sum of current segment > mid
split
}
if total segment > N
start = mid + 1;
else 
update result;
end = mid - 1;
}

Answer 2

找到整个数组的总和并调用该T，并执行k = T / N来确定第一个子数组元素的理想总和。然后线性创建第一个子数组(从数组的开头开始(，同时在决定子数组是否应该/不应该包含下一个元素时尝试最小化k和sum of all values in the sub-array so far + potential next element之间的差异。

然后使用递归将数组的剩余部分拆分为N-1块，N == 1时停止(数组的剩余部分是最后一个子数组(。

注意：这并不能在所有情况下提供最佳解决方案，但它相对较快，并且出于(动态(负载平衡的目的，存在负载经常变化的风险，以至于任何更昂贵的东西(总是找到最佳解决方案(都是没有意义的。