algorithm - 将数组拆分为具有相似权重的子数组

Question

我有一个 n 正数数组。我需要将它拆分成 N 个连续的子数组； n > N.

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

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

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

Answer 1

这个问题等同于在所有 j 上找到 max S(j) 的最小值。

直觉:

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

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

因此，问题归结为在所有 j 上找到 max S(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;
}