最大化 N 个正数中大小为 L 的 K 个不相交且连续的子集的总和

Question

我正在尝试找到一种算法来找到实数数组 x 的大小 L 的 K 不相交的连续子集，使元素的总和最大化。

详细说明，X是N个正实数的集合：
X={x[1],x[2],...x[N]} where x[j]>=0 for all j=1,...,N.

称为 S[i] 的长度 L 的连续子集定义为 X 的 L 个连续成员，从位置 n[i] 开始并在位置 n[i]+L-1 结束：
S[i] = {x[j] | j=n[i],n[i]+1,...,n[i]+L-1} = {x[n[i]],x[n[i]+1],...,x[n[i]+L-1]}.

如果 |n[i]-n[j]|>=L，则两个这样的子集 S[i] 和 S[j] 被称为成对不相交（非重叠）。换句话说，它们不包含 X 的任何相同成员。

定义每个子集的成员求和：

SUM[i] = x[n[i]]+x[n[i]+1]+...+x[n[i]+L-1];

目标是找到长度为 L 的 K 个连续且不相交（非重叠）的子集 S[1],S[2],...,S[K]，使得 SUM[1]+SUM[2]+...+SUM[K] 最大化。

Answer 1

这是动态规划解决的。让 M[i] 成为 x 的前 i 个元素的最佳解决方案。那么：

M[i] = 0 for i < L
M[i] = max(M[i-1], M[i-L] + sum(x[i-L+1] + x[i-L+2] + ... + x[i]))

您的问题的解决方案是M[N]。

编写代码时，您可以逐步计算总和（或简单地预先计算所有总和），从而在 space 和时间上得出 O(N) 的解决方案。

如果您必须精确地找到 K 个子集，您可以通过将 M[i, k] 定义为第一个 i 上具有 k 个子集的最佳解决方案来扩展它元素。那么：

M[i, k] = 0 for i < k * L or k = 0.
M[i, k] = max(M[i-1, k], M[i-L, k-1] + sum(x[i-L+1] + ... + x[i])

您的问题的解决方案是M[N, K]。

这是一个 2d 动态规划解决方案，时间和 space 复杂度为 O(NK)（假设您使用与上述相同的技巧来避免重新计算总和）。