重み付けされていない区間スケジューリングのための動的プログラミングアルゴリズム？

Question

私は、重み付けされていない間隔のスケジューリングのためのDPアルゴリズムについて、誰かが私に理由を教えてくれるかどうか疑問に思っていました。

2つの配列[t1、...、tn]と[d1、...、dn]が与えられます。ここで、tiはジョブiの開始時刻、diはジョブiの期間です。また、ジョブは開始時刻でソートされるので、t1 < = t2 < = ... < = tnです。私は、重複することなく実行できるジョブの数を最大限にする必要があります。私はこの問題のためのDPアルゴリズムとランタイムを考え出しています。どんな助けでも大歓迎です！

ありがとうございました！

Answer 1

私はこの問題に費やす時間はもうありません。ここにアイデアがあります。ダイナミックプログラミングにうってつけだと思います。次のようにと仮定T = {t1, t2, ..., tn}が分割されている

[実際に私が...それはが DPですが、私は最後に、このような事を学ん以来、ほぼ二十年が経過していると思う]：

T = {t1, t2, ..., tn} = {t1, t2, ..., tk} U {tk+1, tk+2, ..., tn} 
    = T1(k) U T2(k) 

はT2'(k)はのサブセットでみようT2(k)のジョブが重複しています。T1(k)。

の値がTの場合、opt(X)を最適値とします。そして、最小はもちろんのいずれかの可能性のあるk in {1, 2, ..., n}

に沿って取られ

opt(T) = min(opt(T1(k)) + opt(T2'(k)) 

あなたは再帰的にopt()を計算し、アカウントの重複を考慮する必要があります。

希望すると便利です。

Answer 2

各ジョブの終了時間を決めて、終了時間が長くなるようにジョブを並べ替えることを考えてみるのが最も簡単ですが、おそらく開始時間を使って同じことを達成できます反対方向に。

終了時間が長い順に各ジョブを検討してください。各ジョブについて、そのジョブを処理することを決定した場合は、そのジョブまで処理できる最大ジョブ数を計算します。これを実行するには、すでに計算した回答を、そのジョブの開始時刻までのカバータイムで調べ、最大ジョブ数をカバーするものを探します。検討している仕事を処理する最善の方法は、その最大数に1を加算することです。

すべてのジョブを考慮した場合、カバーできる最大数は、ジョブを検討するときに計算した最大数です。特定のジョブで可能な限り最大のスコアを計算した後に特定した以前のジョブを保存し、最大スコアを持つジョブからこれらのポインターをトレースすることによって、どのジョブを実行するかを検討することができます。私は、これはO（N^2）