算法帮助:如何将数组划分为具有最小可能最大段的N个段(平衡分段)

我在俄罗斯的一个编程论坛上遇到过这个问题,但还没有提出一个优雅的解决方案.

问题:

你有一个N正整数的数组,你需要将它分成M个连续的段,这样最大的段的总和是最小的可能值.按段的总数,我的意思是所有整数的总和.换句话说,我想要一个平衡良好的数组分割,你不希望单个分段过大.

例:

数组:[4,7,12,5,3,16]

M = 3,意味着我需要将我的数组分成3个子阵列.

解决方案是:[4,7] [12,5] [3,16],以便最大的段是[3,16] = 19,并且没有其他的分段变体可以产生总数较小的最大段.

另一个例子:

数组[3,13,5,7,18,8,20,1]

M = 4

解决方案:[3,13,5] [7,18] [8] [20,1],"最胖"段是[7,18] = 25(纠正我,如果我错了,我编的是这个例子)

我有一种感觉,这是一些经典的CS /数学问题,可能有一些着名人物的名字,如Dijkstra的问题. - 有没有任何已知的解决方案？- 如果没有,你能否提出除暴力强迫之外的其他解决方案,据我所知,时间复杂度,指数.(N ^ M,更具体).

提前谢谢,stackoverflowers.

让我们对答案进行二进制搜索。

对于固定答案X ，很容易检查它是否可行（我们可以使用贪心算法（始终采用可能的最长段，使其总和为<= X），然后将段数与进行比较M）。

总时间复杂度为O(N * log(sum of all elements))。

这是一些伪代码

boolean isFeasible(int[] array, long candidate, int m) {
    // Here goes the greedy algorithm.
    // It finds the minimum number of segments we can get(minSegments).
    ...
    return minSegments <= m;
}

long getMinimumSum(int[] array, int m) {
    long low = 0; // too small
    long high = sum of elements of the array // definitely big enough
    while (high - low > 1) {
         long mid = low + (high - low) / 2;
         if (isFeasible(array, mid, m))
             high = mid;
         else
             low = mid;
    }
    return high;
}