算法帮助:如何将数组划分为具有最小可能最大段的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]
• 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;
}

Answer 2

我喜欢ILoveCoding 的方法。这是另一种需要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 分区：

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

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) 时间。