algorithm - 证明加权任务调度问题的贪心解

Question

我试图证明以下算法是完全正确的（部分正确性+终止），但我似乎只能证明任意示例输入（不是一般输入）。

Here is my pseudo-code:

IN :Listofjobs J, maxindex n

1:S ← an array indexed 0 to n, with null at each index 
2:Sort J in non-increasing order of profits 
3:for i from 0 to n
4:Find the largest t such that S[t] = null and t ≤ J[i].deadline (if one exists) if an index t was found
5: S[t] ← J[i]

OUT: S maximizes the profit of scheduled jobs that can be done in n 1 unit of time blocks

例如，我创建了一个包含工作及其相关属性（截止日期和利润）的表：

jOB        J1   J2  J3  J4  J5
Deadline    2   1   3   2   1
profit     62   100 20  40  20

从这个示例输入中，我们可以做 J2,J1,J3，总利润为 182。

有人可以帮助我形成一种更通用的方式来显示我的伪代码算法是完全正确的吗？

标签： algorithmdynamic-programminggreedyproof-of-correctness

Answer 1

添加约束可以帮助您。

在第 2 步中，首先按非递增利润订购 J，然后按非递增期限订购 J。

在所有最佳解决方案中，至少有一个解决方案必须按照工作利润随时间排序的顺序排在最后。（如果多个工作具有相同的利润和截止日期，则可能存在多个按字典顺序排在最后的最优解决方案。）

证明任何与您放置的第一个工作不同时具有相同利润的工作的解决方案不是最优的，或者在最优解决方案中不是按字典顺序排列的最后一个。

通过归纳证明，您找到的解决方案在放置作业大小方面与任何最佳解决方案相同，并且在最佳解决方案中按字典顺序排在最后。

请注意，这只是一个大纲。这个证明的每一步都需要一些微妙的技巧，我特意把这些技巧留作练习。