2

重複の可能性：
重複する間隔のシーケンスで最大合計を見つけるアルゴリズム

私は次の修正されたアクティビティスケジューリング（欲張りアプローチ）の問題を解決していました：

開始時間Siとfiを含むn個のアクティビティのセットSが与えられた場合、 i番目のアクティビティの終了時間。また、重みwiを考えると、i番目のアクティビティを実行するためにFooが獲得したコスト。

問題は、 fooの収益を最大化するアクティビティを選択することです。fooが獲得できる最大コストを返す必要があります。Fooは一度に1つのアクティビティにしか対応できないと想定します。

ノート：：

これは、従来のアクティビティ選択の問題に似て います。ここでの唯一の違いは、アクティビティごとに、コストwiが与えられることです。そして、ここでの目標はあまりにも異なります-相互に互換性のあるアクティビティの最大サイズのセットを見つける代わりに、この問題では、fooの総収益を最大化するアクティビティのセットを見つける必要があります。

例

Total activities N=4
Si fi wi
0 1 4000
2 5 100
1 4 3000
4 5 2500

Max earning=9500 (Answer)

この問題を解決するために、古典的な欲張り活動選択アルゴリズムを変更するにはどうすればよいですか。上記の問題を解決するには、どのロジックを使用する必要がありますか？

4

1 に答える 1

6

これを貪欲に解決する方法がわかりません。私が見ることができる解決策は動的計画法であり、そこではサブ問題を解決する必要があります

F（n）= Fooがn日目以降にのみ働くことで得られる最大の利益はいくらですか？

次に、再帰的な定式化が明確になります。F（n）はF（n + 1）に等しいか（Fooがn日目に機能しない場合）、またはF（fi ）+ wi、時間si=nで開始する各アクティビティ。

編集：アクティビティの終了時刻がf0 <= f1 <= f2 <= ...<=fNであると仮定します。その場合、答えはF [f0]（時間f0から始まる最高の利益は何ですか）であり、次のように計算できます。

for n = N to 0:
    F[fn] = F[fn+1]
    for each activity (si, fi, wi):
         if si == fn: 
             F[fn] = max(F[fn], F[fi] + wi)

アクティビティが開始時間に基づいて昇順ではない順序でソートされている場合、このアプローチの複雑さはアクティビティの数に比例します（si <Nのときに内部ループを停止できるため）。

于 2012-10-03T05:28:54.173 に答える