私はこの問題を解決しようとしています. N (N<=1000) の間隔が与えられており、アルゴリズムは、サブセット内の 3 つの間隔が共通点を共有しないように、(サイズ) 最大の間隔のサブセットを計算する必要があります。現在、動的計画法のアルゴリズムのみを探しています。
私の考えは、間隔を終了時刻でソートし、次のサブ問題を検討することでした: A[i] - 最初の i 間隔のみを使用した問題の解 (つまり、間隔の最大数)。
そして今、私の質問は再発についてです: i 番目の間隔が取られた場合、再発を理解することはできません。
誰かが私がどこで間違ったのか説明できますか (それは副問題の定義でしたか、それとも再発副問題で何かを見落としているだけですか)?
編集 (新しいアイデア?)
いくつかの調査の後、一般的なジョブ選択アルゴリズムのこのDP ソリューションを見つけました。したがって、次のアイデアはq配列を持つことです。ここで、q[i]= i 番目の間隔と重複しない最後の間隔のインデックスです。そして確かに、i 番目の間隔が取られるときに A[i] を計算する式は次のようになります (欠落部分に注意してください)。
A[i] = 1 + A[q[i]] + [missing-part];
//1 stands for the i-th interval
//A[q[i]] stands for the solution of the intervals that do not overlap with with the i-th interval
//[missing-part] is the maximum number of intervals from the intervals that overlap with the i-th intervals that are safe to be added.
問題は残ります: 不足している部分をどのように計算するのですか?
編集 (望ましい解決策ではなく、貪欲な解決策) 貪欲な解決策は非常に単純で、Job Selection Problemと非常によく似ています。新しい間隔を追加するときに、問題の状態を壊す未処理の間隔が残ってはならないという追加のチェックがあります。