python - 动态规划: find the maximum revenue

Question

这是使用动态规划的 O(N log N) 加权作业调度问题

How each list is structured = [city, start_day, end_day, revenue]
rev = [['A', 1, 7, 5], ['B', 6, 9, 4], ['C', 1, 5, 3]]
>>> print(max_rev(rec))
['B', 6, 9, 4], ['C', 1, 5, 3]

我对 n log n 的尝试:

1. 使用修改后的合并排序根据城市的最后一天对列表进行排序(n log n)，这将得到[['C', 1, 5, 3 ], ['A', 1, 7, 5], ['B', 6, 9, 4]] 现在根据索引将它们编号为 0 -> n (之前提到过插入排序，我搞乱了因为最坏的情况是 n^2，因此我现在使用合并排序)
2. *从这里一无所知。创建一个 n (3) 大小的备忘录列表，memo 的每个索引代表特定城市在现在排序的 rev 中的索引位置
3. 备忘录的每个索引将包含该销售员在该城市工作可以获得的最大收入。为此，请循环遍历排序列表，并针对每个城市信息，将其与 start_day 大于所选城市 end_day 的城市之间的所有收入相加。

Answer 1

你有了一个良好的开端。让我们从您已排序并编号的职位列表开始。

考虑这个问题:“如果你只能从事数字 <= i 的工作，你能赚多少钱”。将此称为money(i)。 money(n-1) 就是您正在寻找的答案。

显然money(0)是作业0的值。

如果您知道之前作业的结果，则可以轻松计算以下作业的

money(i):

money(i) = max(
    money(i-1),  // this is the value if we don't do job i
    job_value(i), // this is the case when we only do job i
    job_value(i) + money(j) // j is the highest value job that ends before i starts
)

现在您只需找到最好的j。您错过的部分是，money(i)总是至少与money(i-1)一样大——这永远不会有坏处有另一份工作可用，因此最好的工作 j 始终是在 i 开始之前结束的编号最高的工作。

由于您的作业列表是按结束时间排序的，因此您可以通过二分搜索在 O(log N) 时间内找到此作业 j，总共的时间复杂度为 O(N log N)。