最大化N个正数中大小为L的K个不连续和连续子集的总和 [英] Maximizing the overall sum of K disjoint and contiguous subsets of size L among N positive numbers

查看:230
本文介绍了最大化N个正数中大小为L的K个不连续和连续子集的总和的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我正在尝试寻找一种算法,以找到数组的 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 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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆