4

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

您将获得一个大小为 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 个子数组。但是，这是指数解决方案，永远不会奏效。

所以我正在寻找解决它的好主意。如果你有请告诉我。

谢谢你的帮助。

4

6 回答 6

5

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

这个想法是对你m将是什么进行二进制搜索 - 然后在数组上贪婪地向前移动，将当前元素添加到分区中，除非添加当前元素将它推到当前m- 在这种情况下你开始一个新的分区。m如果使用的分区数小于或等于您给定的 input ，则当前是成功的（因此调整您的上限） k。否则，您使用了太多分区，并提高了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
 }

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

 for i = 0 to infinity
    if partitions( array, i ) <= k
       return i
于 2011-12-21T18:42:52.103 回答
3

动态规划。做一个数组

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

在哪里best[i][j]可以实现拆分j数组 inti子数组的第一个元素的最佳方法。best[1][j]只是第一个j数组元素的总和。有了 row i，你计算 rowi+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 = ceiling(sum/k)。这是最小值的下限。要找到最小值的良好上限，请通过任何上述方法创建一个良好的分区，移动边界，直到找不到任何仍然会减小最大子和的简单移动。这给了你一个上限 B，不比下限大很多（如果它大得多，我认为通过移动边框你会发现一个简单的改进）。现在继续使用 ChingPing 的算法，已知的上限减少了可能的分支数量。最后一个阶段是 O((BA)*n)，发现B未知，但我猜比 O(n^2) 更好。

于 2011-12-21T15:58:50.053 回答
2

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

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

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

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

于 2011-12-21T15:59:12.907 回答
1

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

你开始说均匀分布的分离（实际上你如何开始并不重要）。

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

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

编辑：查看@rds 的评论。您将不得不更加努力地考虑弹跳解决方案和最终条件。

于 2011-12-21T16:11:09.940 回答
0

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

从那里

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

我的想法，不幸的是不起作用：

  1. 将数组拆分为 N 个子数组
  2. 找到总和最小的两个连续子数组
  3. 合并步骤 2 中找到的子数组以形成一个新的连续子数组
  4. 如果子数组的总数大于 k，则从步骤 2 开始迭代，否则结束。
于 2011-12-21T16:20:19.050 回答