問題は、古典的な加重間隔スケジューリングの問題がありますが、追加の要件があります。この要件は、与えられたジョブから、いくつかのジョブを実行する必要があるということです。
私はすでにブルートフォースでそれを解決しています。しかし、私はより効率的な解決策が必要です。動的計画法で古典的な重み付きスケジューリング問題を解きますが、この制約では解けません。何か提案はありますか。アドバイスありがとうございます。
2 に答える
0
さて、この問題が従来の加重間隔スケジューリングとどのように大きく異なるのかわかりません。「やらなければならない」仕事が重複していない場合（もしそうなら、定義が不明確な問題があります-2つの重複する「やらなければならない」仕事の間でどのように選択するのですか？）、それらの相対的な重みを立てる方法が必要です。残りの仕事のうち。
O(n) でジョブをトラバースし、最大の重みを見つけることができます。次に、「実行する必要がある」ジョブの場合、その最大値を重みに追加する必要があります。これにより、優先度の低いジョブよりも相対的な重みが確実に高くなるため、他のジョブよりも確実に選択されるようになります。
私が言ったように、唯一の問題は、「やらなければならない」仕事が重なっている場合です。その場合、いくつかの必須ジョブが選択されていない状態で終了します (1 つの必須ジョブを選択する必要があるため)。
于 2013-11-16T09:01:21.633 に答える
0
従来のスケジューリング問題に基づいて、もう 1 つのディメンションを追加するだけです
その次元は、これまでに行われたジョブの数を示します
例えば。
f[i][j] は、時間 i で j 個のジョブが実行されたときの最大利益を意味します
f[i][j] は f[job_end_time[k]][j+1] を決定できます job_start_time[k]>=i
于 2013-01-11T08:50:36.660 に答える