2

S整数のシーケンスと正のN整数が与えられた場合W、それらの合計の重みが正確にWであり、それらの合計が最大になるような、重複しない間隔のセットを見つけます。

For a chosen interval [i,j]:

 - Weight([i,j]) = j-i+1 
 - Sum([i,j]) = S[i+1] + S[i+2] + ... + S[j].

例

S = (12, 9, 1, 2, 8, -1), W = 4  

Choose [1,2] and [4,5] with total_sum = Sum([1,2]) + Sum([4,5]) = 9 + 8 = 17

(12 9 _ 2 8 _)

この問題は、ナップサック問題と加重間隔スケジューリングに少し似ていますが、これははるかに簡単な方法で解決できると思います。

私の考えは動的計画法を使用してletを使用することでしたがP[i][k] be the maximum total sum of the first i elements, using only k elements、答えはですがP[N][W]、サブ問題間の関係を思い付くことができませんでした。

4

2 に答える 2

1

左から右に作業する場合、これまでの回答を次のように要約できます。

1) 重量

2) その答えの一番右の間隔の右端

3) 区間内の要素の合計

したがって、各段階で、右端の間隔の右端と総重量の可能な組み合わせごとに、最大合計で答えを追跡する場合、左から右に実行される動的プログラムでこれを解決できると思います。

于 2013-03-10T13:36:59.177 に答える
0

そうではありませんか：

  f[i][j]= MAX( f[i-1][j] , f[i-T][j-Weight[i-T,i]]+Sum[i-T,i] );

で答えが得られますf[N][W]。O(N^2W)このソリューションをより良いものに最適化する方法があるはずです。しかし、あなたはより速いものを求めなかったので...

于 2013-03-10T13:53:49.327 に答える