最大化N个正数中大小为L的K个不连续和连续子集的总和 [英] Maximizing the overall sum of K disjoint and contiguous subsets of size L among N positive numbers
问题描述
我正在尝试寻找一种算法,以找到数组的 L
个不相交的连续子集 x
实数可以使元素的总和最大化。
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.
详细说明细节,X是一组N个正实数:
X = {x [1],x [2],... x [N]}其中,对于所有x [j]> = 0 j = 1,...,N。
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.
长度为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]}。
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]}.
两个这样的子集 S [i]
和 S [j]
被称为成对不相交(不重叠),如果 | n [i] -n [j ] |> = L
。换句话说,它们不包含X的任何相同成员。
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.
定义每个子集成员的总和:
Define the summation of the members of each subset:
SUM[i] = x[n[i]]+x[n[i]+1]+...+x[n[i]+L-1];
目标是找到K个连续且不相交(不重叠)的子集 S [1],S [2],...,S [K]
的长度为L,使得 SUM [1] + SUM [2] + ... + SUM [K]
已最大化。
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.
推荐答案
这是通过动态编程解决的。让 M [i]
仅是 x <的前
i
个元素的最佳解决方案/ code>。然后:
This is solved by dynamic programming. Let M[i]
be the best solution only for the first i
elements of x
. Then:
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]
。
The solution to your problem is M[N]
.
编写代码时,您可以递增地计算总和(或简单地预先计算所有总和),得出O( 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.
如果您必须精确地找到 K
子集,可以通过定义 M [i,k]
来扩展此范围,以使其成为 k $ c的最优解前
i
个元素上的$ c>个子集。然后:
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:
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
)(假设您使用与上述相同的技巧来避免重新计算总和)。
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).
这篇关于最大化N个正数中大小为L的K个不连续和连续子集的总和的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!