加權作業排程演算法
加權作業排程演算法也可以表示為加權活動選擇演算法。
問題是，鑑於某些工作的開始時間和結束時間，以及你在完成工作時獲得的利潤，如果沒有兩個工作可以並行執行，你可以獲得的最大利潤是多少？
這個看起來像使用貪婪演算法的活動選擇，但有一個額外的扭曲。也就是說，我們專注於實現最大利潤，而不是最大化完成的工作數量。執行的工作數量與此無關。
我們來看一個例子：
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | A | B | C | D | E | F |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (2,5) | (6,7) | (7,9) | (1,3) | (5,8) | (4,6) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 6 | 4 | 2 | 5 | 11 | 5 |
+-------------------------+---------+---------+---------+---------+---------+---------+
這些工作用名稱，開始和結束時間以及利潤來表示。經過幾次迭代後，我們可以看出我們是否執行了 Job-A 和 Job-E ，我們可以獲得 17 的最大利潤。現在如何使用演算法找到它？
我們做的第一件事就是按照非遞減順序對作業進行整理。我們為什麼要做這個？這是因為如果我們選擇一個花費較少時間完成的工作，那麼我們會留出大部分時間來選擇其他工作。我們有：
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
我們將有一個大小為 n 的臨時陣列 Acc_Prof （這裡， n 表示作業總數）。這將包含執行作業的最大累計利潤。不明白嗎？等等看。我們將使用每個作業的利潤初始化陣列的值。這意味著， Acc_Prof [i] 將首先保持執行第 i 個工作的利潤。 **** **** **** ****
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
現在，讓我們表示位置 2 與我，以及 1 位將被記 Ĵ 。我們的策略是將 j 從 1 迭代到 **i-1，**並且在每次迭代之後，我們將 i 遞增 1，直到 i 變為 n + 1 。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
我們檢查工作[I] 和工作[J] 重疊，也就是說，如果完成時間的工作[J] 大於工作[I] 的開始時間，那麼這兩個作業不能一起做。但是，如果它們不重疊，我們將檢查 Acc_Prof [j] + Profit [i]> Acc_Prof [i] 。如果是這種情況，我們將更新 Acc_Prof [i] = Acc_Prof [j] + Profit [i] 。那是：
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
這裡 Acc_Prof [j] +利潤[i] 代表完成這兩項工作的累計利潤。我們來看看它的例子：
在這裡工作[J] 重疊與作業[I] 。所以這些不能一起完成。由於我們的 j 等於 i-1 ，我們將 i 的值增加到 i + 1 ，即 3 。我們使 j = 1 。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
現在 Job [j] 和 Job [i] 不重疊。通過選擇這兩個工作我們可以獲得的總利潤是： Acc_Prof [j] + Profit [i] = 5 + 5 = 10 ，它大於 Acc_Prof [i] 。所以我們更新 Acc_Prof [i] = 10 。我們也將 j 增加 1.我們得到了，
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
在這裡，作業[j]的重疊與作業[I] 和 Ĵ 也等於 I-1 。所以我們將 i 遞增 1，並使 j = 1 。我們得到了，
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
現在， Job [j] 和 Job [i] 不重疊，我們得到累計利潤 5 + 4 = 9 ，這大於 Acc_Prof [i] 。我們更新 Acc_Prof [i] = 9 並將 j 遞增 1。
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 9 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
同樣工作[J] 和工作[I] 不重疊。累計利潤為： 6 + 4 = 10 ，大於 Acc_Prof [i] 。我們再次更新 Acc_Prof [i] = 10 。我們將 j 增加 1.我們得到：
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 10 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
如果我們繼續這個過程，在使用 i 迭代整個表之後，我們的表最終將如下所示：
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 14 | 17 | 8 |
+-------------------------+---------+---------+---------+---------+---------+---------+
*已跳過幾個步驟以縮短文件。
如果我們遍歷陣列 Acc_Prof ，我們可以找出最大利潤為 17 ！ 虛擬碼：
Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
for j -> 1 to i-1
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
endfor
endfor
maxProfit = 0
for i -> 1 to n
if maxProfit < Acc_Prof[i]
maxProfit = Acc_Prof[i]
return maxProfit
填充 Acc_Prof 陣列的複雜性為 **O（n 2 ）。**陣列遍歷取 O(n) 。因此該演算法的總複雜度為 O（n 2 ）。
現在，如果我們要找出哪些進行的工作，以獲得最大的利潤，我們需要遍歷以相反的順序排列，如果 Acc_Prof 匹配 MAXPROFIT ，我們將推動名字的作業堆疊，並減去利潤的來自 maxProfit 的那份工作。我們將這樣做，直到我們的 maxProfit> 0 或我們到達 Acc_Prof 陣列的起始點。虛擬碼看起來像：
Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
if maxProfit is equal to Acc_Prof[i]
S.push(Job[i].name
maxProfit = maxProfit - Job[i].profit
endif
endfor
該程式的複雜性為： O(n) 。
有一點需要記住，如果有多個工作時間表可以給我們帶來最大的利潤，我們只能通過這個程式找到一個工作時間表。