在N个正数中最大限度地使大小为L的K个不连续子集的总和最大

I'm trying to find an algorithm to find K disjoint, contiguous subsets of size L of an array x of real numbers that maximize the sum of the elements.

我想找一个算法来找到K个不相交的，相邻的大小为L的数组x的实数，使元素的和最大化。

Spelling out the details, X is a set of N positive real numbers:
X={x[1],x[2],...x[N]} where x[j]>=0 for all j=1,...,N.

详细说明，X是一组N个正实数:X={X [1]， X[2]，…x[N]}其中x[j]>=0，所有j=1，…，N。

A contiguous subset of length L called S[i] is defined as L consecutive members of X starting at position n[i] and ending at position 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]}.

一个长度为L的连续子集叫做S[i]，定义为X的连续成员，从n[i]开始，到n[i]+L-1: S[i] = {X [j] | j=n[i]，n[i]+1，…n[我]+ l - 1 } = { x[n[我]],[n[我]+ 1],…,x[n[我]+ l - 1]}。

Two of such subsets S[i] and S[j] are called pairwise disjoint (non-overlapping) if |n[i]-n[j]|>=L. In other words, they don't contain any identical members of X.

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

Define the summation of the members of each subset:

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

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

The goal is find K contiguous and disjoint(non-overlapping) subsets S[1],S[2],...,S[K] of length L such that SUM[1]+SUM[2]+...+SUM[K] is maximized.

我们的目标是找到K个连续的和不相交的(非重叠的)子集S[1]，S[2]，…，S[K]的长度为L，即[1]+[2]+…+[K]和最大化。

1 个解决方案

#1

This is solved by dynamic programming. Let M[i] be the best solution only for the first i elements of x. Then:

这可以通过动态规划来解决。设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]))

The solution to your problem is M[N].

解决你的问题的方法是M[N]。

When you code it, you can incrementally compute the sum (or simply pre-compute all the sums) leading to an O(N) solution in both space and time.

当您编写它时，您可以增量地计算总和(或者简单地预先计算所有的和)，从而在空间和时间上得到O(N)解。

If you have to find exactly K subsets, you can extend this, by defining M[i, k] to be the optimal solution with k subsets on the first i elements. Then:

如果你必须找到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])

The solution to your problem is M[N, K].

你的问题的解决方法是M[N, K]。

This is a 2d dynamic programming solution, and has time and space complexity of O(NK) (assuming you use the same trick as above for avoiding re-computing the sum).

这是一个2d动态编程解决方案，具有O(NK)的时间和空间复杂性(假设您使用与上面相同的技巧来避免重新计算和)。

#1