3

動的計画法の割り当てを受けましたが、漸化式を理解するのに助けが必要です。この問題は加重間隔の問題に似ていますが、いくつかの追加の制限があります。

  • Nそれぞれ同じ期間の一連のタイムスロットが与えられます。
  • 各タイムスロット、、kに0 <= k < Nは正の重みが与えられW[k]ます。
  • [i, j]が付いている時間間隔の場合、その間隔i < jの重みは次のようになります。最初のタイムスロット の重みはカウントされないため、長さの間隔の重みは。になります。W[i,j]
    W[i,j] = W[i+1] + W[i+2] + ... + W[j]
    W[i]10

値が与えられ、選択した時間間隔の合計が最大になるようT < Nに正確にタイムスロットを選択するように求められます。T

例：N = 5、、およびT = 4重みの場合、とW = (3, 9, 1, 1, 7)を選択するW[0, 1] = 9とW[3, 4] = 7、の最大重みがになり16ます。

4

1 に答える 1

5

これはちょっとした問題です...選択された最後のスロット（最後の範囲の終わり）がiで、スロット0..iの中に正確にt個のスロットが選択されている場合、可能な最大の重みになるようにS（i、t）を定義します。

DPの決定は、w [i]をS（i、t）に追加するか、スロットi-1が選択されたか、選択されなかったために追加しないかです。だから私たちは持っています：

S(i, t) = max ( S(i-1, t-1) + w[i], S(j, t-1) for j = t-2..i-2 )

t-1>iが無意味な場合。したがって、基本ケースは0 <= i <Nの場合はS（i、1）= 0であり、DPテーブルの連続する列（t = 2、...、T）はそれぞれ最後の列よりも短くなります。望ましい答えはmax（j = T-1..N-1の場合はS（j、T））です。

幸い、最大値が漸増的に計算され、実行時間はO（NT）、スペースはO（N）になるように計算を調整できます。

例を実行すると、DPテーブルは次のようになります。

               t = 
         1    2    3    4
       ------------------
i = 0 |  0
    1 |  0    9   
    2 |  0    1   10
    3 |  0    1    9   11
    4 |  0    7    9   16

答えはmax（11、16）=16です

于 2013-03-09T18:59:46.490 に答える