加权作业调度算法
加权作业调度算法也可以表示为加权活动选择算法。
问题是，鉴于某些工作的开始时间和结束时间，以及你在完成工作时获得的利润，如果没有两个工作可以并行执行，你可以获得的最大利润是多少？
这个看起来像使用贪婪算法的活动选择，但有一个额外的扭曲。也就是说，我们专注于实现最大利润，而不是最大化完成的工作数量。执行的工作数量与此无关。
我们来看一个例子：
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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) 。
有一点需要记住，如果有多个工作时间表可以给我们带来最大的利润，我们只能通过这个程序找到一个工作时间表。