28

私が解決しようとしている問題には、数直線上の間隔のリストがあり、それぞれに事前定義されたスコアがあります。可能な最大の合計スコアを返す必要があります。

キャッチは、間隔が重複していることです。重複する間隔のうち、使用できるのは 1 つだけです。ここに例があります。

Intervals   - Score  
   0- 5     -  15  
   4- 9     -  18  
  10-15     -  12  
   8-21     -  19  
  25-30     -  25

ここでは、間隔 0 ～ 5、4 ～ 9、および 8 ～ 21 が重なります。
間隔 10-15 と 8-21 も重なります。
最大合計は 55 (18+12+25) です。

ここで、3 つの中で最高のスコアを持っていなくても、重複する間隔の最初のバッチの間隔 4 ～ 9 を選択することに注意することが重要です。

これは、間隔 8 ～ 21 を選択すると、後で間隔 10 ～ 15 を使用できなくなり、全体の合計が減少するためです (この場合、全体の合計は 19 + 25 = 44 になります)。

この問題に対する O(nlogn) または O(n) ソリューションを探しています。動的計画法が使えると思いますが、間違っているかもしれません。誰かがここでトリックを実行できるソリューション/アルゴリズムを提案できますか?

編集：間隔は特定の順序ではありません。

4

6 に答える 6

26

これは、インターバルスケジューリングの加重バリエーションです。動的計画法O(N log N)で解決できます。

間隔をg(start, stop, score)、とし、それらを。でソートしstopます。stop簡単にするために、今のところすべてが一意であると仮定しましょう。

best[i]使用が許可されたときに取得できる最高のスコアにしましょうg[1], ..., g[i]。もちろん、すべてを使用する必要はありません。使用する間隔のサブセットは重複しないようにする必要があるため、通常は使用できません。

  • 明らかbest[0] = 0に。つまり、間隔を使用できないため、取得できる最高のスコアは0です。
  • いずれ1 <= k <= Nの場合も、次のようになります。
    • best[k] = max( best[k-1], best[j] + g[k].score )、 どこ
      • jg[j].stop < g[k].start（jゼロになる可能性がある）のような最大のインデックスです

つまり、使用が許可されている場合g[1], ... g[k]、実行できる最善の方法は、次の2つのオプションのスコアを上げることです。

  • は含まれていませんg[k]。したがって、このオプションのスコアはですbest[k-1]。
    • ...それが私たちにできる最善のことだからg[1], ... g[k-1]
  • を含めg[k]、その左側には、重複しないすべての遺伝子、つまりすべての遺伝子を可能g[k]なg[1], ..., g[j]限り大きくして、できる限りのことを行います。したがって、このオプションのスコアはです。g[j].stop < g[k].startjbest[j] + g[k].score

（上記の方程式で具体化された動的計画法の最適な部分構造と重複する部分問題のコンポーネントに注意してください）。

質問に対する全体的な答えはbest[N]、つまり、すべての遺伝子の使用を許可されたときに取得できる最高のスコアです。おっと、私は遺伝子を言いましたか？私は間隔を意味します。

これは、次のO(N log N)理由によるものです。

  • すべての間隔を並べ替えるにはO(N log N)
  • それぞれjの検索kはO(log N)二分探索を使用しています

複数の遺伝子が同じstop値を持つことができる場合、何も変更されません。それでも、右端を検索する必要がありますj。たとえばPythonでは、これは簡単bisect_rightです。標準ライブラリのバイナリ検索で同点の場合に返されるインデックスが保証されないJavaでは、（多くのオプションの中で）線形検索（O(N)最悪の場合のパフォーマンス）または別の一連のバイナリ検索を実行して検索できます。右端のインデックス。

おっと、私は再び遺伝子を言いましたか？私は間隔を意味します。

関連する質問

于 2010-07-14T09:58:39.467 に答える
4

まず、最大値は 55 ではなく 59 だと思います。間隔 [0-5]、[8-21]、および [25,30] を選択すると、15+19+25=59 になります。これを処理するには、ある種の動的計画法を使用できます。

最初に、すべての間隔を開始点で並べ替え、次に端から端まで繰り返します。リスト内の各項目について、その時点から最後までの最大合計を として選択しますmax(S[i]+S[j], S[i+1])。ここで、i は現在の項目、j は項目に続く最初の重複しないエントリ (つまり、最初の項目) です。その開始が現在のアイテムの終了よりも大きい)。アルゴリズムを高速化するには、各要素の最大部分和 S[j] を格納します。

明確にするために、これに従ってあなたの例を解決させてください。まず、間隔を並べ替えます。

 1:  0- 5 -  15
 2:  4- 9 -  18
 3:  8-21 -  19
 4: 10-15 -  12
 5: 25-30 -  25

そう、

 S[5] = 25
 S[4] = max(12+S[5], 25)=37
 S[3] = max(19+S[5], S[4])=max(19+25,37)=44
 S[2] = max(18+S[4], S[3])=max(18+37,44)=55
 S[1] = max(15+S[3], S[2])=max(15+44, 55)=59

これは、この投稿のアルゴリズムの適応ですが、残念ながら、O(n) の実行時間は適切ではありません。各エントリが次のエントリと重複する縮退リストでは、O(n^2) になります。

于 2010-07-14T07:55:32.740 に答える
0

これを少し考えて、何か思いついた。

区間木は、特定の区間と重なるすべての区間を見つける効率的な方法を提供します。間隔のセット全体を歩くと、特定の間隔の重複するすべての間隔を見つけることができます。これらを取得したら、スコアが最も高い間隔を見つけて保存し、次に進みます。

ツリーの構築にはO（N Log N）時間がかかり、ルックアップにはO（Log N）時間がかかります。すべての要素をルックアップするため、解はO（N Log N）になります。

ただし、上記の例のように、1つのグループの最高スコア間隔で合計が減少する場合、最高スコア間隔を事前に使用してはならないことを知る方法がないため、アルゴリズムは失敗します。これを回避する明白な方法は、確信が持てない場合に両方（またはすべて）の合計を計算することですが、それは潜在的にO（N ^ 2）またはより悪い解決策に戻ります。

于 2010-07-14T15:39:06.230 に答える
0

この再帰を使用できると思います...

S[i]各区間のスコアを
Interval[i]示す すべての区間を示す

ResMax[i] = max(ResMax[i-1] + S[i] //if i is included
           ,max(R[i-1],S[i]) 
         )

私は完全にチェックされていませんが、うまくいくはずです。

于 2011-10-21T03:32:32.483 に答える
0

おそらく、この回答のようなアプローチを使用できます。これは、少なくともその問題ではO(n)です。これは、間隔を 1 回反復し、最適な最終解につながる可能性のある間隔の組み合わせだけを追跡することを意味します。

于 2010-07-14T03:49:50.933 に答える
0

ナップザック問題のバリエーションのように聞こえます。これらのソリューションを検索する際に、何らかのインスピレーションが得られるかもしれません。

私たちは何回の間隔について話しているのですか？（あなたの例のように）約5の場合は、すべての組み合わせを試す方がおそらくより実用的です. それ以上の場合、理想解の近似値でよいでしょうか? ここでも、ナップザック ソリューション (George Dantzig の貪欲な近似アルゴリズムなど) から始めるのがよいでしょう。

于 2010-07-14T03:52:21.283 に答える