将数组分成K部分

Question

让数组

 A[0] = 2
  A[1] = 1
  A[2] = 5
  A[3] = 1
  A[4] = 2
  A[5] = 2
  A[6] = 2

我需要将数组分成K个部分，使得较大的总和最小。
例如，当k=3时。

[2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15;
[2], [1, 5, 1, 2], [2, 2] with a large sum of 9;
[2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8;
[2, 1], [5, 1], [2, 2, 2] with a large sum of 6.

所以算法应该返回6。
我应该使用哪个算法，这是修改过的KMP算法吗？
请提供一种方法。

- user4018473

---

数组中有哪些元素？如果只有正数，那么问题会变得更加简单。如果只有正的有限范围整数（例如32位无符号整数），那么问题会更加简单。 - Evgeny Kluev

@EvgenyKluev 只有正数在那里。 - user4018473

对于这种情况，David的答案可能是你能得到的最好的。 - Evgeny Kluev

Answer 1

我认为你可以使用动态规划来解决这个问题。这样想——如果你做了一次切割，把前m个元素放在第一组中，那么得到的最大值将是前m个元素的和与将最后n-m个元素切成k-1段所能得到的最小值之和的最小值。作为基本情况，如果你用完了所有元素，那么最小值就是∞。

更正式地说，令S[n, k]表示使用数组前n个元素且必须进行k次切割时你能够构造出的最小的最大值。你可以写出以下递归式:

S[0, k] = ∞ 任何k (如果数组中没有元素且必须切割任意次数，则值为无限大)。

S[n, k] = min_{m ≤ n}{max(A[n]+A[n-1]+...+A[n-m], S[n-m,k-1])} 当n>0时（你从后面取出一些元素，计算min作为最佳选择）。

你需要填充一个Θ(nk)的表格，填充位置(n',k')的元素需要Θ(n')的时间。因此，总运行时间将为Θ(n²k)。

作为启发式方法，你可能可以稍微加速一下。特别地，当A[n]+A[n-1]+...+A[m]变得大于S[n-m,k-1]时，你就知道你已经把太多的元素放进了前面的组中，因此可以停止评估更大的m值。这只是一种启发式方法，但在实践中可能会带来一些性能上的优势。

希望这对你有所帮助！

- templatetypedef

---

@user4018473 你能详细说明一下吗？ - templatetypedef

该算法的时间复杂度很高，因此这就是为什么。 - user4018473

@user4018473 你能更详细地描述一下你所面临的问题吗？这是为了编程竞赛、作业还是娱乐？输入数据有多大？你已经尝试过什么了？ - templatetypedef

我已经使用了分治算法（类似于最大子数组和问题），这只是为了提高我的算法技能。 - user4018473

Answer 2

有一种针对templatetypedef的DP问题的O(kn)时间优化方法，其工作原理如下。设P(i, j)为将前j个元素分成i个部分时最后一个子数组边界的最佳位置，则P(i, j)在i上是非降的。我们利用这个事实来进行优化（使用Python进行轻微测试）。

def minmaxsum(A, k):
    S = [0]  # partial sums
    for x in A:
        S.append(S[-1] + x)
    n = len(A)
    # V0 is the optimal objective values for the (i, j) subproblems
    V0 = [1e309] * (n + 1)  # 1e309 is infinity
    V0[0] = 0
    for j in range(k):
        # V1 is the optimal objective values for the (i + 1, j) subproblems
        V1 = []
        i0 = 0
        for i1 in range(n + 1):
            # the while loop is amortized constant-time
            while i0 < n and \
                    max(V0[i0], S[i1] - S[i0]) >= \
                        max(V0[i0 + 1], S[i1] - S[i0 + 1]):
                i0 += 1
            V1.append(max(V0[i0], S[i1] - S[i0]))
        V0 = V1
    return V0[n]

为了进一步改进这个解决方案，在足够“平滑”的输入上，我们观察到sum(A) / k是任何解决方案成本的下限。因此，对于在i处的分割，我们有下限max(sum(A[:i]) / (k - 1), sum(A[i:]))。使用这个下限，我们可以使用二分搜索来找到最可能的分割点，然后只评估少量的DP条目，使用下限来排除其余的。

- David Eisenstat