带权区间调度问题的变种：每个区间有一个执行概率，求期望最大收益
字数 2211 2025-12-22 09:00:15

带权区间调度问题的变种：每个区间有一个执行概率，求期望最大收益

问题描述

我们有一个任务列表，每个任务用一个区间 [start, end) 表示其执行时间，并附带两个属性：

  • 权重（收益）value：如果成功执行该任务，可以获得的收益。
  • 成功概率 prob：一个在 [0, 1] 范围内的浮点数，表示该任务独立执行的成功概率。

如果一个任务被执行但失败了，则收益为0。你的目标是选择一组互不重叠的任务（即选出的任意两个任务的执行区间不能重叠），使得这组任务的总期望收益最大。

注意：

  • 任务的成功与否是独立的。
  • 你可以在多个任务中选择，但它们的时间不能重叠。
  • 期望收益的计算：对于选中的任务集合，每个任务的贡献是 value * prob，总期望收益就是这些贡献的和。

我们需要计算最大可能的期望收益。

解题思路

这个问题的基本结构是经典的带权区间调度，但我们把每个任务的固定权重（收益）替换为期望收益（value * prob），这样可以直接应用经典算法吗？

答案是：可以，但需要注意任务是否成功的独立性。由于任务之间是否成功是独立的，并且我们只关心期望值，而期望具有可加性（即使随机变量独立，和的期望等于期望的和），因此我们可以将每个任务的期望收益 value * prob 视为其“权重”，然后直接使用带权区间调度的动态规划解法。

为什么可以这样？

  • 设我们选择了一个任务集合 S。
  • 总实际收益是一个随机变量，等于 S 中各个任务实际收益（成功时为 value，失败时为 0）的和。
  • 总期望收益 = Σ (每个任务的收益期望) = Σ (value_i * prob_i)，因为独立随机变量和的期望等于期望的和。
  • 因此，最大化期望收益等价于最大化这些“期望权重”的和。

这样，问题就转化为：给定一系列带时间区间和权重（期望收益）的任务，选出互不重叠的任务使得权重和最大。

解决步骤

步骤1：预处理

  1. 将任务按照结束时间 end 升序排序。这是经典区间调度的常见做法，便于查找不重叠的前驱任务。
  2. 对每个任务 i（排序后），计算其“期望权重” w[i] = value[i] * prob[i]。

步骤2：定义状态

设 dp[i] 表示考虑前 i 个任务（按结束时间排序后的前 i 个）时，能获得的最大期望收益。

步骤3：状态转移

对于每个任务 i，有两种选择：

  • 不选任务 i：则 dp[i] = dp[i-1]。
  • 选任务 i：则需要找到前 i-1 个任务中，最后一个结束时间 ≤ 任务 i 开始时间的任务，记其索引为 p[i]。那么选了任务 i 后，最大期望收益为 w[i] + dp[p[i]]。

因此：

dp[i] = max(dp[i-1], w[i] + dp[p[i]])

步骤4：计算 p[i]

p[i] 是最大的索引 j（j < i）使得任务 j 的结束时间 ≤ 任务 i 的开始时间。由于任务已按结束时间排序，我们可以用二分查找快速计算：

  • 对每个任务 i，在 [0, i-1] 范围内二分查找最后一个满足 end[j] ≤ start[i] 的 j。
  • 如果找不到，则 p[i] = 0（我们约定 dp[0] = 0，表示没有任务时的收益为0）。

步骤5：初始化

  • 添加一个虚拟任务 0，dp[0] = 0，便于处理边界。
  • 排序后的任务从 1 开始编号。

步骤6：最终答案

答案为 dp[n]，其中 n 是任务数量。

举例说明

假设有 3 个任务（已按结束时间排序）：

  1. 区间 [1, 4)，value=10，prob=0.8 → w=8.0
  2. 区间 [3, 5)，value=5，prob=0.6 → w=3.0
  3. 区间 [0, 6)，value=20，prob=0.5 → w=10.0

计算 p[i]：

  • 任务1：开始=1，前面无任务 → p[1]=0
  • 任务2：开始=3，前面任务1结束=4 > 3，不满足；找不到 → p[2]=0
  • 任务3：开始=0，前面无任务 → p[3]=0

动态规划表（n=3）：

  • dp[0] = 0
  • i=1：dp[1] = max(dp[0], 8+dp[0]) = max(0, 8)=8
  • i=2：dp[2] = max(dp[1], 3+dp[0]) = max(8, 3)=8
  • i=3：dp[3] = max(dp[2], 10+dp[0]) = max(8, 10)=10

最大期望收益 = 10（选择任务3单独执行，期望收益 20*0.5=10）。

时间与空间复杂度

  • 排序：O(n log n)
  • 计算 p[i]：n 次二分查找，每次 O(log n)，总 O(n log n)
  • 动态规划：O(n)
  • 总时间复杂度：O(n log n)
  • 空间复杂度：O(n) 存储任务信息、p 数组和 dp 数组。

关键点总结

  1. 由于期望的线性性质，我们可以将每个任务的期望收益作为权重，从而将原问题转化为经典的带权区间调度问题。
  2. 经典解法是按结束时间排序后动态规划，用二分查找快速定位不重叠的前驱。
  3. 最终结果是一个浮点数（最大期望收益），注意计算时的精度处理（通常 double 类型足够）。

这个变种在概念上很有趣，它展示了如何将概率期望自然地融入确定性优化框架中，只要目标函数是线性的。

带权区间调度问题的变种：每个区间有一个执行概率，求期望最大收益 问题描述 我们有一个任务列表，每个任务用一个区间 [start, end) 表示其执行时间，并附带两个属性： 权重（收益） value ：如果成功执行该任务，可以获得的收益。 成功概率 prob ：一个在 [0, 1] 范围内的浮点数，表示该任务独立执行的成功概率。 如果一个任务被执行但失败了，则收益为0。你的目标是选择一组 互不重叠 的任务（即选出的任意两个任务的执行区间不能重叠），使得这组任务的总 期望收益 最大。 注意： 任务的成功与否是独立的。 你可以在多个任务中选择，但它们的时间不能重叠。 期望收益的计算：对于选中的任务集合，每个任务的贡献是 value * prob ，总期望收益就是这些贡献的和。 我们需要计算最大可能的期望收益。 解题思路 这个问题的基本结构是经典的 带权区间调度 ，但我们把每个任务的固定权重（收益）替换为 期望收益 （ value * prob ），这样可以直接应用经典算法吗？ 答案是： 可以，但需要注意任务是否成功的独立性 。由于任务之间是否成功是独立的，并且我们只关心 期望值 ，而期望具有可加性（即使随机变量独立，和的期望等于期望的和），因此我们可以将每个任务的期望收益 value * prob 视为其“权重”，然后直接使用带权区间调度的动态规划解法。 为什么可以这样？ 设我们选择了一个任务集合 S。 总实际收益是一个随机变量，等于 S 中各个任务实际收益（成功时为 value，失败时为 0）的和。 总期望收益 = Σ (每个任务的收益期望) = Σ (value_ i * prob_ i)，因为独立随机变量和的期望等于期望的和。 因此， 最大化期望收益等价于最大化这些“期望权重”的和 。 这样，问题就转化为：给定一系列带时间区间和权重（期望收益）的任务，选出互不重叠的任务使得权重和最大。 解决步骤 步骤1：预处理 将任务按照结束时间 end 升序排序。这是经典区间调度的常见做法，便于查找不重叠的前驱任务。 对每个任务 i（排序后），计算其“期望权重” w[i] = value[i] * prob[i] 。 步骤2：定义状态 设 dp[i] 表示考虑前 i 个任务（按结束时间排序后的前 i 个）时，能获得的最大期望收益。 步骤3：状态转移 对于每个任务 i，有两种选择： 不选任务 i ：则 dp[i] = dp[i-1] 。 选任务 i ：则需要找到前 i-1 个任务中，最后一个结束时间 ≤ 任务 i 开始时间的任务，记其索引为 p[i] 。那么选了任务 i 后，最大期望收益为 w[i] + dp[p[i]] 。 因此： 步骤4：计算 p[ i ] p[i] 是最大的索引 j（j < i）使得任务 j 的结束时间 ≤ 任务 i 的开始时间。由于任务已按结束时间排序，我们可以用二分查找快速计算： 对每个任务 i，在 [0, i-1] 范围内二分查找最后一个满足 end[j] ≤ start[i] 的 j。 如果找不到，则 p[i] = 0 （我们约定 dp[ 0 ] = 0，表示没有任务时的收益为0）。 步骤5：初始化 添加一个虚拟任务 0， dp[0] = 0 ，便于处理边界。 排序后的任务从 1 开始编号。 步骤6：最终答案 答案为 dp[n] ，其中 n 是任务数量。 举例说明 假设有 3 个任务（已按结束时间排序）： 区间 [ 1, 4)，value=10，prob=0.8 → w=8.0 区间 [ 3, 5)，value=5，prob=0.6 → w=3.0 区间 [ 0, 6)，value=20，prob=0.5 → w=10.0 计算 p[ i ]： 任务1：开始=1，前面无任务 → p[ 1 ]=0 任务2：开始=3，前面任务1结束=4 > 3，不满足；找不到 → p[ 2 ]=0 任务3：开始=0，前面无任务 → p[ 3 ]=0 动态规划表（n=3）： dp[ 0 ] = 0 i=1：dp[ 1] = max(dp[ 0], 8+dp[ 0 ]) = max(0, 8)=8 i=2：dp[ 2] = max(dp[ 1], 3+dp[ 0 ]) = max(8, 3)=8 i=3：dp[ 3] = max(dp[ 2], 10+dp[ 0 ]) = max(8, 10)=10 最大期望收益 = 10（选择任务3单独执行，期望收益 20* 0.5=10）。 时间与空间复杂度 排序：O(n log n) 计算 p[ i ]：n 次二分查找，每次 O(log n)，总 O(n log n) 动态规划：O(n) 总时间复杂度：O(n log n) 空间复杂度：O(n) 存储任务信息、p 数组和 dp 数组。 关键点总结 由于期望的线性性质，我们可以将每个任务的期望收益作为权重，从而将原问题转化为经典的带权区间调度问题。 经典解法是按结束时间排序后动态规划，用二分查找快速定位不重叠的前驱。 最终结果是一个浮点数（最大期望收益），注意计算时的精度处理（通常 double 类型足够）。 这个变种在概念上很有趣，它展示了如何将概率期望自然地融入确定性优化框架中，只要目标函数是线性的。