活动选择贪婪方法（已修改） [英] Activity selection greedy approach (modified)

问题描述

可能重复：

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

I was solving the following modified activity scheduling (Greedy approach) problem :

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

Given a set S of n activities with and start time, Si and fi, finish time of an ith activity. Also given weight wi ,the cost earned by Foo for doing ith activities.

问题是要选择最大化foo收入的活动。我们必须返回foo可以赚取的最大成本。假设Foo一次只能从事一项活动。

The problem is to select the activities that maximizes foo earnings. We have to return the maximum cost that can be earn by foo.Assume that Foo can only work on a single activity at a time.

注意：

这类似于经典的活动选择问题，这里唯一的区别是，对于每项活动，我们都会得到wi的费用。而且这里的目标太不同了-不是找到相互兼容的活动的最大规模集，在这个问题中，我们必须找到使总收入最大化的那些活动集。

This is similar to classic Activity selection problem ,here the only difference is ,for each activities ,we are given a cost wi . And the goal here is too different -Instead of finding maximum size set of mutually compatible activities ,In this problem we have to find set of those activities that maximise foo total earnings .

示例

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

Max earning=9500 (Answer)

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

How do i modify the classical greedy activity selection algorithm ,for solving this problem . What logic should i use to solve the above problem?

推荐答案

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

I don't see how to solve this greedily. The solution I can see is dynamic programming, in which you have to solve the subproblem

F（n）= Foo仅在工作后才能获得的最大利润是多少？第n天？

F(n) = what is the maximum profit that Foo can get by working only after day n?

然后，递归公式很清楚：我们有F（n）等于F（n + 1）（在Foo不对于在时间si = n上开始的每个活动，在第n天不起作用，或等于F（fi）+ wi中的最大值。

Then the recursive formulation is clear: We have that F(n) is either equal to F(n+1) (in the case in which Foo doesn't work on day n), or equal to the maximum out of F(fi) + wi, for each activity that starts on time si=n .

编辑：假设活动的结束时间是f0 ＜＝ f1 ＜＝ f2 ＜＝ ... ＜fN。答案是F [f0]（从时间f0开始的最佳利润是什么），可以计算为：

Suppose the ending times of the activities are f0 <= f1 <= f2 <= ... <= fN. Then the answer is F[f0] (what is the best profit working starting on time f0), and it can be calculated as:

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时，您可以停止内循环）。

If the activities are sorted in non-increasing order based on their starting time, the complexity of this approach is linear in the number of activities (as you can stop the inner loop when si < N).

这篇关于活动选择贪婪方法（已修改）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！