は重みが関連付けられている一連の活動、総重量

Question

私は考え、この問題の解決策を探しているを最大化する、非重複活動のセットを選択考えると、wikipedia

でこれを見つけました解決策は、終了時間でアクティビティを見つけることを提案する。< = iの開始時間。 しかし、この例で考えてみます。

-開始時間：[1,2,3,4,5]

-終了時間：[3,4,5,6,7]

それぞれ - 重量：[13,5,2,4,1]

この例では、私がアクティビティ：（4-6）を実行しているとき、私は4時間未満のアクティビティを2つ持っているので、バイナリ検索で数値を検索するのではなく、配列を返してから最大値を取ってはいけません。

私がそのコンセプトを誤解している場合は、私に修正してください。

Answer 1

opt[i] = MAX(opt[i-1], opt[t] + w(i))の記事によると、opt[i]は、ithの前に終了するすべてのアクティビティを考慮しています。そのため、すべての可能なオプションを反復する必要はありません。