algorithm - Interval 赚取的最大利润

Question

我们必须将汽车租给客户。我们有一个列表，其中每个元素代表提供汽车的时间，第二个 -> 汽车归还的时间，第三个 -> 借出的利润。所以我需要找出可以赚取的最大利润。

例如:

( [1,2,20], [3,6,15], [2,8,25], [7,12,18], [13,31,22] )

赚取的最大利润为 75。[1,2] + [3,6] + [7,12] + [13,31]。

我们可以有重叠的间隔。我们需要选择使我们的利润最大化的案例。

Answer 1

假设你只有一辆车，那么我们在Weighted Interval Scheduling中解决的问题

假设我们有区间 I₀ , I₁, I₂, ....I_n-1 和间隔 I_i 是 (s_i,t_i,p_i)

算法:

1. 首先根据起点 s_i 对区间进行排序。

2. 为动态规划创建一个数组，MaxProfit[i] 表示您可以从区间 I_i,I_i+1,I< sub>n-1.初始化最后一个值

           MaxProfit[n-1] = profit_of_(n-1)
   

3. 然后使用 DP 我们可以找到最大利润:

   一个。要么我们可以忽略给定的区间，在这种情况下，我们的最大利润将是我们可以从剩余区间获得的最大利润

           MaxProfit[i+1]
   

   或者我们可以包括这个区间，在这种情况下，最大利润可以写成

           profit_of_i + MaxProfit[r]
   

   其中 r 是满足 s_r> t_i 的下一个区间所以我们的整体 DP 变成了

           MaxProfit[i] = max{MaxProfit[i+1], profit_of_i + MaxProfit[r] }
   

   1. 返回MaxProfit[0]的值