我试图概括Paul Hankin在_640672中提供的算法,这样解决方案不仅限于每个子集的大小都是L,并且目标不是最大化总和,而是返回具有最大子集的集合 .
详细说明, X
是一组 N
正实数: X={x[1],x[2],...x[N]} where x[j]>=0 for all j=1,...,N
.
一个名为 S[i]
的连续子集由 up to L
X
的连续成员组成,从 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]}, where l=1,...,L
.
如果它们不包含 X
的任何相同成员,则这些子集中的两个 S[i]
和 S[j]
被称为成对不相交(非重叠) .
定义每个子集成员的总和:
SUM[i] = x[n[i]]+x[n[i]+1]+...+x[n[i]+l-1]
目标是找到连续且不相交(非重叠)的子集 S[1],S[2],...
,其长度范围从 1 to L
尽可能大并涵盖 X
的所有 N
元素 .
例如,给定 X = {5,6,7,100,100,7,8,5,4,4}
和 L = 4
,解决方案是 S[1] = {5,6,7}, S[2] = {100, 100, 7, 8}, and S[3] = {5,4,4}
,这样 SUM[1] = 18, SUM[2] = 215, and SUM[3] = 13
. 虽然总和,无论子集,总是 246
,但关键是长度范围为 1 to L
的其他子集不会产生比上面提供的更大的 SUM[i]
.
任何帮助是极大的赞赏 .
2 回答
我稍后会清理代码,但这是我提出的解决方案 .
Sub getLargestEvents()
'算法改编自Maximizing the overall sum of K disjoint and contiguous subsets of size L among N positive numbers
结束子
这是一个更好的解决方案: