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

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( n d ))

这个想法是对你的 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