-1

要素の合計を最大化する実数の配列のKサイズのばらばらで連続したサブセットを見つけるアルゴリズムを見つけようとしています。Lx

詳細を説明すると、X は N 個の正の実数のセットです。
X={x[1],x[2],...x[N]} where x[j]>=0 for all j=1,...,N.

呼び出される長さ L の連続するサブセットは、 position で始まり positionで終わる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]}.

そのような部分集合のうちの 2 つ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]

4

1 に答える 1

2

これは動的計画法によって解決されます。の最初の要素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].

これは 2 次元の動的プログラミング ソリューションであり、O( ) の時間と空間の複雑さがありNKます (合計の再計算を回避するために上記と同じトリックを使用すると仮定します)。

于 2015-03-26T00:06:39.733 に答える