algorithm - 活动选择贪心法（修改）

Question

可能重复：
在一系列重叠间隔中找到最大和的算法

我正在解决以下修改后的活动调度（贪婪方法）问题：

给定一组 S 的 n 个活动，开始时间为Si和fi，完成第 i 个活动的时间。还给定权重wi，Foo 进行 ith 活动所赚取的成本。

问题是选择使 foo 收益最大化的活动。我们必须返回 foo 可以赚取的最大成本。假设 Foo 一次只能处理一个活动。

笔记：：

这类似于经典的活动选择问题，这里唯一的区别是，对于每个活动，我们都被赋予了一个成本 wi。而且这里的目标太不同了——而不是找到最大大小的相互兼容的活动集，在这个问题中，我们必须找到最大化 foo 总收益的那些活动集。

例子

Total activities N=4
Si fi wi
0 1 4000
2 5 100
1 4 3000
4 5 2500

Max earning=9500 (Answer)

我如何修改经典的贪婪活动选择算法来解决这个问题。我应该使用什么逻辑来解决上述问题？

score 6 · Accepted Answer

我不知道如何贪婪地解决这个问题。我可以看到的解决方案是动态编程，您必须在其中解决子问题

F(n) = Foo 仅在第 n 天后工作所能获得的最大利润是多少？

然后递归公式很清楚：我们有 F(n) 要么等于 F(n+1)（在 Foo 在第 n 天不工作的情况下），要么等于 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 时停止内部循环）。

1 回答 1