1

加重間隔スケジューリングの問題は次のとおりです。加重間隔のセットが与えられた場合、合計加重が最大になるように重複しない間隔のセットを選択します。加重間隔 x は、トリプル x = (s, f, v) で表すことができます。ここで、s=x の開始時間、f=x の終了時間、v=x の重みまたは値 これらの加重間隔は、次のように表すことができます。トリプル (0,3,3) (1,4,2) (0,5,4) (3,6,1) (4,7,2) (3,9,5) (5,10,2) ) (8,10,1) 加重間隔スケジューリング問題の解を計算するプログラムを書きなさい。ここにグラフの写真があります: http://imgur.com/vZn04xn

プログラムは、最適解の合計重みの値と選択された区間のインデックスを出力する必要があります。上記の場合、出力は次のようになります (この出力は正しくありません) 最適値: 7 間隔シーケンス: 2 5 プログラムは再帰を使用する必要があります。

最適値を計算するアルゴリズムは次のとおりです。 入力: n, s1,...,sn , f1,...,fn , v1,...,vn

f1 > f2 >... > fn となるようにジョブを終了時刻で並べ替えます。p(1)、p(2)、...、p(n) を計算します。ここで、p(j) = 最大インデックス i < j で、ジョブ i は j と互換性があります。

for j = 1 to n
   M[j] = empty <-- solution table
M[j] = 0

M-Compute-Opt(j) {
   if (M[j] is empty)
      M[j] = max(wj + M-Compute-Opt(p(j)), M-Compute-Opt(j-1))
   return M[j]
}

start、finish、weight の 3 つの int を持つクラス Job を作成しました。サイズ 8 の配列の各スポットに異なる間隔のそれぞれを持つタイプのジョブの配列があります。質問: 各ジョブ間隔の p を計算するにはどうすればよいですか?

4

2 に答える 2

0

動的計画法で解決できる問題のように聞こえます。

1 から n までの i ごとに、スケジュールできる最大の重みと、これらの重みに使用された最後の間隔の終了日を保存します。興味深い可能な重みのみを保存します。たとえば、間隔 1+4 (w=4) は間隔 3 (w=4) よりも興味深いものではありません。これは、間隔 3 (w=4) が前者の前に終了し、合計の重みが同じであるためです。

動的計画法の秘訣は、1 から n まで 1 項目ずつ移動することです。各ステップで、そのステップで利用可能な新しいデータがより良い答え、別の可能な答え、またはより悪い答えにつながるかどうかを判断します。次のステップに進む前に、より適切で異なる回答のみを保存する必要があります。

date    max weight  last interval
1       0           0
2       0           0
3       3           1
4       3           1
5       3 or 4      1 or 3 
6       4           3
7       4 or 5      3 or 5
8       4 or 5      3 or 5
9       5 or 8      5 or 6 
10      last step is for you, if I did not make mistakes in other rounds...
于 2013-10-28T13:49:18.533 に答える
0

これは役立つかもしれません.....

public static int p(int index){
    for(int i=(index-1); i >=0; i--){
        if(f[i] <= s[index-1])  return i;
    }
    return -1;
}
于 2015-11-05T02:36:44.927 に答える