算法帮助：如何将数组分成N段，尽可能少的最大段（平衡分段）

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]
男=4

解法：[3, 13, 5] [7, 18] [8] [20, 1]，"fattest"段为[7, 18] = 25（有误请指正, 这个例子是我编的)

我觉得这是一些经典的 CS/math 问题，可能与某个名人的名字相关联，例如 Dijkstra 问题。 - 是否有任何已知的解决方案？ - 如果没有，你能想出除了暴力破解之外的其他解决方案吗，据我所知，时间复杂度是 exponential.（N^M，更具体）。

提前致谢，Whosebugers。

Answer 1

让我们对答案进行二分查找。
对于一个固定的答案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;
}

Answer 2

我喜欢。这是另一种方法，需要 O(MN^2) 时间，如果 N 和 M 很小但数组中的数字非常大（具体来说，如果 log(sum) >> MN，这是可能的，但不可否认听起来不太现实）。它使用动态规划。

让我们考虑仅将由前 i <= N 个条目组成的子数组划分为 j <= M 个段。设 f(i, j) 是该子问题最佳解决方案中最大段的权重——即前 i 个数字的第 j 个分区中最大段的权重，其最大段在所有此类分区中最小。我们要计算f(N, M)，以及与之对应的一个（可能不止一个）分区。

计算 f(i, 1) 很容易——它只是前 i 个元素的总和:

f(i, 1) = x[1] + ... + x[i]

要为 j >= 2 计算 f(i, j)，请注意元素 i 必须是从某个位置 1 <= k <= i 开始且前面有 j 的某个段的最后一个元素-1 段 -- 并且在参数 (i, j) 的任何最优解中，前面的那些 j-1 段必须本身对于参数 (k-1, j-1) 是最优的。因此，如果我们考虑最后一段的每个可能的起始位置 k 并取最佳位置，我们将计算前 i 个元素的最佳 j 分区：

[编辑 3/2/2015：我们需要取新段的最大值和最大的剩余段，而不是相加！]

f(i, j >= 2) = minimum of (max(f(k-1, j-1), x[k] + ... + x[i])) over all 1 <= k <= i

如果我们按降序尝试 k 个值，那么我们可以很容易地在恒定时间内为每个 k 个值建立总和，因此计算单个 f(i, j) 值需要 O(N) 时间。我们有 MN 个这些值要计算，因此所需的总时间为 O(MN^2)。

还需要一个边界条件来禁止尝试分割成比元素多的段：

f(i, j > i) = infinity

一旦我们计算出 f(N, M)，我们就可以通过以通常方式回溯 DP 矩阵来提取相应的分区——但在这种情况下，使用 ILoveCoding 构建分区可能更容易贪心算法。无论哪种方式都需要 O(N) 时间。

算法帮助：如何将数组分成N段，尽可能少的最大段（平衡分段）

Algorithm help: how to divide array into N segments with least possible largest segment (balanced segmenting)

arrays

algorithm

optimization