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

Question

我试图找到一种算法来找到一个实数数组的K大小不相交的连续子集，以最大化元素的总和。Lx

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

称为长度 L 的连续子集S[i]定义为 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]}.

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

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

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

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

Answer 1

这是通过动态规划解决的。让成为 的第一个元素M[i]的最佳解决方案。然后：ix

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]。

编写代码时，您可以增量计算总和（或简单地预先计算所有总和），从而N在空间和时间上产生 O(·) 解决方案。

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

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]。

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