従来の重み付き区間スケジューリング問題では、リストがあります。 {i_1, ..., i_n} 重み付き区間の数 w_j。重み付き区間スケジューリング問題を解くためのアルゴリズムを示した。 ここに そしてこれは基本的な動的計画法の問題です。 しかし、スケジュール内で、選択された間隔の重みがその前の間隔の重みに依存している（そして順番に重みが順序に依存している）場合、どうなりますか？例は w_j" = w_j"*(w_(j-1)" + 1) プライミングされた変数が固有の重みである場合プライムされていない重みは、順序を考慮した「実際の」重み、つまり、目的関数に実際に使用する重みです。この問題はNP困難ですか？それは確かにそれのように聞こえます。
編集：これをより簡単に（現実的に）するために、離散的な単位時間を仮定しましょう。
回答：
回答№1は0さて、私はそれを考え出しました。アルゴリズムは（私が間違っていたら私に直してください）：
for t in times:
if is_first(t):
best_candidate = None
else:
best_candidate = best(t - 1)
for interval in intervals if interval.end_time is t:
value_i = f(best(interval.start_time) + interval)
value_candidate = f(best_candidate)
if value_i > value_candidate:
best_candidate = best(interval.start_time) + interval
best(t) = best_candidate
return best(times[-1])
どこでコレクション times, intervals インターバルの潜在的なタイムストップとインターバル自体 f 目的関数です。
繰り返し間の定数は次のとおりです。 t 終了しました、 best(t) で終わる最良のスケジュールです t。初期化ステップのため、 best(t) == best(t - 1) 可能です。また、私のコメントのように、これは以下の場合にのみ有効です。 f のように単調増加 f その前の間隔に基づいて個々の間隔に適用されることを意味します。私は速記としてここでのやり方でそれを使います。