需要解决这个算法难题的想法

Question

我过去遇到过一些与此类似的问题，但我仍然不知道如何解决这个问题。问题是这样的：

给你一个正整数数组，大小为 n <= 1000 且 k <= n，这是你必须将数组分割成的连续子数组的数量。您必须输出最小值 m，其中 m = max{s[1],..., s[k]}，并且 s[i] 是第 i 个子数组的总和。数组中的所有整数都在 1 到 100 之间。示例：

Input:                           Output:
5  3  >> n = 5 k = 3             3
2 1 1 2 3

将数组拆分为 2+1 | 1+2 | 3 将最小化 m。

我的蛮力想法是使第一个子数组在位置 i 结束（对于所有可能的 i），然后尝试以最佳方式将数组的其余部分拆分为 k-1 个子数组。然而，这是指数解决方案，永远不会起作用。

所以我正在寻找好的想法来解决它。如果你有的话请告诉我。

感谢您的帮助。

Answer 1

您可以使用动态规划来解决这个问题，但实际上您可以通过对答案进行贪心和二分搜索来解决。该算法的复杂度为 O(n log d)，其中 d 是输出答案。 （上限是数组中所有元素的总和。）（或输出位大小的 O( nd ) ）

这个想法是对您的 进行二分搜索m 将是 - 然后在数组上贪婪地向前移动，将当前元素添加到分区中，除非添加当前元素将其推到当前 m 之上 - 在这种情况下，您启动一​​个新分区。如果使用的分区数量小于或等于给定的输入k，则当前的m 成功（从而调整您的上限）。否则，您使用了太多分区，并提高 m 的下限。

一些伪代码：

// binary search
binary_search ( array, N, k ) {
    lower = max( array ), upper = sum( array )

    while lower < upper {
        mid = ( lower + upper ) / 2

        // if the greedy is good
        if partitions( array, mid ) <= k
           upper = mid
        else
           lower = mid
    }
 }

 partitions( array, m ) {
    count = 0
    running_sum = 0

    for x in array {
       if running_sum + x > m
          running_sum = 0
          count++
       running_sum += x
    }
    if running_sum > 0
       count++
    return count
 }

这应该更容易从概念上提出。另请注意，由于分区函数的单调性质，如果您确定输出 d 不太大，您实际上可以跳过二分搜索并进行线性搜索：

 for i = 0 to infinity
    if partitions( array, i ) <= k
       return i

Answer 2

动态规划。创建一个数组

int best[k+1][n+1];

，其中 best[i][j] 是最好的分割数组 int i 子数组的前 j 元素的方法。 best[1][j] 只是前 j 数组元素的总和。有了 i 行，您可以按如下方式计算行 i+1：

for(j = i+1; j <= n; ++j){
    temp = min(best[i][i], arraysum[i+1 .. j]);
    for(h = i+1; h < j; ++h){
        if (min(best[i][h], arraysum[h+1 .. j]) < temp){
            temp = min(best[i][h], arraysum[h+1 .. j]);
        }
    }
    best[i+1][j] = temp;
}

best[m][n] 将包含解决方案。该算法是 O(n^2*k)，可能有更好的算法。

编辑：ChingPing、toto2、Coffee on Mars 和 rds 的想法的组合（按照我当前看到此页面的顺序）。

设置A =上限(sum/k)。这是最小值的下限。要找到最小值的良好上限，请通过任何提到的方法创建一个良好的分区，移动边界，直到找不到任何仍会减少最大总和的简单移动。这给了你一个上限 B，不比下限大很多（如果它大得多，我认为通过移动边框你会发现一个简单的改进）。
现在继续 ChingPing 的算法，利用已知的上限减少可能的分支数量。最后一个阶段的时间复杂度为 O((BA)*n)，发现 B 未知，但我猜比 O(n^2) 更好。

Answer 3

我有一个糟糕的分支定界算法（请不要对我投反对票）

首先将数组和 dvide 的总和乘以 k，这为您提供了答案的最佳情况限制，即平均 A。此外，我们将保留迄今为止看到的最佳解决方案对于任何分支 GO（全局最优）。让我们考虑在某个数组元素后面放置一个分隔符（逻辑）作为分区单元，并且我们必须放置 k-1 个分区。现在我们将以这种方式贪婪地放置分区，

遍历数组元素将它们相加，直到您看到在下一个位置我们将超过 A，现在创建两个分支，一个将分隔符放置在该位置，另一个分支放置在下一个位置位置，递归地执行此操作并设置 GO = min（GO，回答分支）。
如果在任何分支中的任何点，我们有一个大于 GO 的分区，或者位置数小于我们绑定的剩余分区。最后你的回答应该是“GO”。

编辑：
正如 Daniel 所建议的，我们可以稍微修改分隔符放置策略，直到达到元素总和为 A 或剩余位置少于分隔符为止。

Answer 4

这只是一个想法的草图......我不确定它是否有效，但它非常简单（而且可能也很快）。

你可以从均匀分布间隔开始（实际上如何开始并不重要）。

对每个子数组求和。
找到总和最大的子数组。
查看左右相邻子数组，如果左侧子数组的总和小于右侧子数组的总和，则将左侧的间隔移动 1（反之亦然）。
对当前总和最大的子数组重做。

你会遇到一些情况，你会不断地在相同的两个位置之间跳跃，这可能意味着你有解决方案。

编辑：请参阅@rds的评论。您必须更加努力地考虑弹跳解决方案和最终条件。

Answer 5

我的想法，不幸的是行不通：

1. 将数组拆分为 N 个子数组
2. 找到总和最小的两个连续子数组
3. 将步骤 2 中找到的子数组合并，形成一个新的连续子数组
4. 如果子数组总数大于 k，则迭代从步骤 2 开始，否则完成。

Answer 6

如果你的数组有随机数，你可以希望每个子数组都有 n/k 的分区是一个很好的起点。

从那里

1. 通过计算和
2. 存储该候选解决方案来评估该候选解决方案。例如：
   • 每个子数组的索引数组
   • 子数组的总和的相应最大值
3. 减少最大子数组的大小：创建两个新候选者：一个子数组从索引+1开始；另一个子数组从index+1开始。子数组以索引 1 结尾的一个
4. 评估新候选者。
   • 如果它们的最大值更高，则丢弃
   • 如果它们的最大值较低，则迭代 2，除非该候选值已被评估，在这种情况下它就是解决方案。