arrays - 算法帮助 : how to divide array into N segments with least possible largest segment (balanced segmenting)

Question

我在一个俄罗斯编程论坛上遇到了这个问题，但还没有想出一个优雅的解决方案。

问题:

你有一个包含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。

Answer 1

1. 让我们对答案进行二分搜索。

2. 固定答案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;
}