动态规划：寻找最大收益

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:

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

Answer 1

您想比较计划，而不仅仅是个别城市。尽管个别城市可以为我们的决定提供信息，但重要的收入是计划之一。

您的示例允许 2 个计划：A(5) 和 CB(7)。

在更复杂的情况下，您可能会有一棵可能性树：

start ---> A(5)
       |
       |-> B ---> C(6)
       |      |
       |      \-> D(4)
       |-> C(3)
       \-> D(1)

我会使用回溯法找到最佳解决方案。

在这个简单的例子中，alpha-beta 修剪似乎也会立即减少搜索 space。

如果你能计算出每天的最大收入，你就可以更积极地修剪。

Answer 2

你开了个好头。让我们从您排序和编号的工作列表开始。

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

显然money(0)是job 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)。

动态规划：寻找最大收益

Dynamic programming: find the maximum revenue

python

algorithm

dynamic-programming