algorithm - 证明贪心算法的最优性

Question

我遇到的问题如下:

我们有 n 个任务，l_i 和 w_i 是任务 i 的完成时间和权重。想出一个算法，使 sum for all i of f_i * w_i 最小化，其中 f_i 是任务 i 完成的时间。例如，如果某个任务 i 首先被调度，那么 f_i = t_i 如果是第二个则 f_i = t_i + t_(first task)。

我花了一些时间在这上面，我最初认为通过从最高权重到最低权重选择任务来简单地制作任务列表就足够了，但意识到这是错误的，例如，如果我们有 2 个任务:

1 个任务:w_i = 10, l_i = 100

2 任务:w_i = 9, l_i = 1

如果我们首先选择 w_i 为 10 的那个，那么我们将得到 10*100 + 9*101 = 1909，但如果我们第二次选择它，我们将得到 9*1 + 10*101 = 1019。

现在我认为最佳算法是从 w_i/l_i 的最高比率到最低比率来安排任务的算法，但我不确定如何证明这一点。有人可以帮忙吗？

Answer 1

你应该能够证明，如果任务没有按照你建议的那样安排，你可以通过交换两个顺序错误的相邻任务来改进时间表。如果你减去这两种情况的总加权完成时间，你最终应该会看到一个表达式来表示类似的东西的加权完成时间的差异

L1W1 + (L1 + L2)W2 - [L2W2 + (L2 + L1)W1] 并发现如果 L1/W1 和 L2/W2 的比较方向错误，则可以通过颠倒顺序获得 yield 。