在java中使用遞歸的加權區間調度

加權區間調度問題是這樣的：給定一組加權區間，選擇一組非加權區間，使得總權重最大。加權間隔x可由三元組表示，其中 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 在java中使用遞歸的加權區間調度

程序應該打印出最佳溶液的總重量的值和所選擇的時間間隔的索引。在上述情況下，輸出會是類似的（此輸出不正確）最佳值：7 間隔序列：2 5 程序務必使用遞歸。

用於計算的最佳值的算法爲：輸入：N，S1，...，SN，F1，...，FN，V1，...，VN通過結束時間

排序作業所以f1> f2> ...> fn。（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] 
}

我創建了一個具有3個整數的類：開始，結束和重量。我有一個類型的作業數組，每個大小爲8的數組中的每個不同的間隔。問題：如何爲每個作業間隔計算p？

來源

2013-10-27 Jonny Forney

聽起來像一個可以用動態規劃解決的問題。

對於從1到n的每個i，保存您可以計劃的最大權重以及用於這些權重的最後時間間隔的結束日期。你只存儲有趣的權重。例如，間隔1 + 4（w = 4）比間隔3（w = 4）更不感興趣，因爲後者在前者之前結束，並且總權重相同。

動態編程的訣竅是將一個項目從1移動到n。在每一步中，找出在該步驟中可用的新數據是否導致更好的答案，不同的可能答案或更差的答案。在轉移到下一步之前，只需要保存更好和不同的答案。

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-28 13:49:18

這可能有助於.....

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-05 02:36:44

在java中使用遞歸的加權區間調度

回答

相關問題