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

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- 在这种情况下,你启动一个新的分区.m如果使用的分区数小于或等于给定输入,则当前成功(因此调整上限)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
 }

这在概念上应该更容易提出.另请注意,由于分区功能的单调性,如果您确定输出d不是太大,您实际上可以跳过二分查找并进行线性搜索:

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