algorithm - 事件选择贪心法(修改)

Question

<分区>

Answer 1

我不知道如何贪婪地解决这个问题。我能看到的解决方案是动态规划，其中你必须解决子问题

F(n) = Foo 在第 n 天后才工作可以获得的最大利润是多少？

那么递归公式就很清楚了:我们有 F(n) 要么等于 F(n+1)(在第 n 天 Foo 不工作的情况下)，要么等于F(fi) + wi，对于每个在时间 si=n 开始的事件。

编辑:假设事件的结束时间是 f0 <= f1 <= f2 <= ... <= fN。则答案为 F[f0](从时间 f0 开始的最佳利润是多少)，可以计算为:

for n = N to 0:
    F[fn] = F[fn+1]
    for each activity (si, fi, wi):
         if si == fn: 
             F[fn] = max(F[fn], F[fi] + wi)

如果事件根据开始时间按非递增顺序排序，则此方法的复杂度与事件数量成线性关系(因为您可以在 si < N 时停止内部循环)。