需要想法解决这个算法谜 [英] Need idea for solving this algorithm puzzle

问题描述

我遇到一些类似的问题来到了这个在过去，我仍然没有得到很好的想法如何解决这个问题。问题是这样的：

I've came across some similar problems to this one in the past, and I still haven't got good idea how to solve this problem. Problem goes like this:

正在给出大小为n℃的正整数数组; = 1000且K = N的是连续的子阵，你将有你的数组分割成数。你必须输出最小m，其中m =最大{S [1]，...，S [k]的}，和s [i]为第i子阵列的总和。阵列中的所有整数是100之间1和实施例：

You are given an positive integer array with size n <= 1000 and k <= n which is the number of contiguous subarrays that you will have to split your array into. You have to output minimum m, where m = max{s[1],..., s[k]}, and s[i] is the sum of the i-th subarray. All integers in the array are between 1 and 100. Example :

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

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

Splitting array into 2+1 | 1+2 | 3 will minimize the m.

我的蛮力的想法是使在位置第一子阵最后，我（对所有可能的我），然后尝试在尽可能最好的方式阵列的其余部分分割为K-1子阵。然而，这是指数溶液和行不通。

My brute force idea was to make first subarray end at position i (for all possible i) and then try to split the rest of the array in k-1 subarrays in the best way possible. However, this is exponential solution and will never work.

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

So I'm looking for good ideas to solve it. If you have one please tell me.

感谢您的帮助。

推荐答案

您可以使用动态规划来解决这个问题，但实际上你可以解决与答案贪婪和二进制搜索。该算法的复杂度是 O（N日志D），其中 D 是输出的答案。 （上界是在阵列中的所有元素的总和。）（或 O（nd）为中的输出位的大小）

You can use dynamic programming to solve this problem, but you can actually solve with greedy and binary search on the answer. This algorithm's complexity is O(n log d), where d is the output answer. (An upper bound would be the sum of all the elements in the array.) (or O( n d ) in the size of the output bits)

我们的想法是对二进制搜索你的米将是 - 然后贪婪地向前移动的阵列上，将当前元素的分区，除非将当前元素在当前推动它 M - 在这种情况下，你开始一个新的分区。目前 M 是成功的（并因此调整上限），如果使用的分区的数量小于或等于你给定的输入 K 。否则，你用了太多的分区，并提高您的下界 M 。

The idea is to binary search on what your m would be - and then greedily move forward on the array, adding the current element to the partition unless adding the current element pushes it over the current m -- in that case you start a new partition. The current m is a success (and thus adjust your upper bound) if the numbers of partition used is less than or equal to your given input k. Otherwise, you used too many partitions, and raise your lower bound on m.

一些伪code：

// 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 是不是太大：

This should be easier to come up with conceptually. Also note that because of the monotonic nature of the partitions function, you can actually skip the binary search and do a linear search, if you are sure that the output d is not too big:

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

这篇关于需要想法解决这个算法谜的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！