5.1 题目描述

区间调度问题：有n项工作，每项工作分别在si开始，fi结束。对每项工作，你都可以选择参加或不参加，但选择了参加某项工作就必须至始至终参加，全程参与，即参与工作的时间段不能有重叠(即使开始的时间和结束的时间重叠都不行)。
这个问题在贪心算法一节习题中出现过。原来的目标是使得你能参与的工作数量最多。但是现在我们对每个工作赋予一个权值，它可能表示这项工作你能获得的报酬。请问，你应该选择哪些工作，才能使得你获得的报酬最多。
这个问题也被称为区间调度问题。如图2.4，按照贪心策略，先后选择活动1和活动3，它们是相容的，但是你能获得的总报酬为2,没有只从事工作2获得的报酬多。请你设计算法，帮助我们选择最优的活动方案。
image.png
图2.4 任务分配

5.2 程序使用说明

  1. 输入任务个数n；
    2. 依次输入数据每个任务的开始时间tasks[i][0]、结束时间tasks[i][1]、价值tasks[i][2]；
    3. 输入任务最终结束时间lastTime。

    5.3 分析和设计

  2. 思路
    对于第i个任务有两种选择方案，即做与不做，如果选择做第i个任务，那么获得的最大价值就是当前任务价值加上前i-1个任务在第i个任务开始之前所获取的最大值，而如果选择不做第i个任务，那么获得的最大价值就是前i-1个任务在第i个任务结束的时间条件下获得的最大价值。为了获得最优解，需要对两种方案进行比较，也就是说需要知道前i-1个物品在不同时间下可获得的最大价值，所以有递推公式F(i, t) = max(F(i-1, t), F(i-1, tasks[i][0])+tasks[i][2])，当然如果时间t没有超过任务结束时间，那么该任务就不能选择，F(i, t) = F(i-1, t)。运用动态规划的思想，自顶向下依次求解第i个物品在时间轴的不同选择获得的最大价值并记录到数组中。数组的最后一个值就是就是获得的最大价值。
    2. 伪代码
    1. ChooseTask(tasks[1...n, 0...2], lastTime)
    2. // 输入：任务信息tasks，tasks[i][0]、tasks[i][1]、tasks[i][2]分别表示//           任务的开发时间、结束时间、价值，任务的最后结束时间lastTime
    3. // 输出：路径
    4. maxValue[0...n][0...lastTime] <- 0
    5. // 自顶向下依次计算每个任务在时间轴上的安排所获得的最大值
    6. for i <- 1 to n do
    7.  for j <- 1 to lastTime do
    8.      if j < task[i, 1]
    9.          // j时，任务未结束
    10.          maxValue[i, j] <- maxValue[i-1, j]
    11.      else 
    12.          maxValue[i, j] <- max(maxValue[i-1,j], tasks[i, 2]+maxValue[i-1, tasks[i, 0]])
    13. // 逆推出选择方案
    14. choose[1...n] <- 0
    15. nowTime <- lastTime
    16. for i <- n to 1 do
    17.  if maxValue[i, nowTime] = maxValue[i-1, nowTime]
    18.      // 没有选择任务i
    19.      choose[i] <- 0
    20.  else
    21.      choose[i] <- 1
    22.      nowTime <- tasks[i, 0]
    23. return choose
  3. 时间复杂度
    在动态规划中，时间复杂度就是把数组填充完成的时间，所以时间复杂度为O(n*leastTime)。

    5.4 测试用例

    | | | | | | | —- | —- | —- | —- | —- | | 1 | n = 3
    tasks = [[1, 3, 2],
    [4, 6, 4],
    [7, 9, 1]]
    lastTime = 9 | 7 | 7 | 通过 | | 2 | n = 3
    tasks = [[4, 5, 2],
    [4, 6, 4],
    [7, 9, 1]]
    lastTime = 9 | 5 | 5 | 通过 | | 3 | n = 3
    tasks= [[3, 5, 2],
    [2, 6, 4],
    [5, 9, 1]]
    lastTime = 9 | 4 | 4 | 通过 |

5.5 源代码（含注释）

  1. import java.util.Scanner;
  2. public class TaskManage {
  3.     public static void main(String[] args) {
  4.         int[][] tasks = new int[][]{{0, 0, 0},{3, 5, 2},{4, 6, 4},{5, 9, 1}};
  5.         int leastTime = 9;
  6.         System.out.println("案例\n3 5 2\n2 6 4\n5 9 1");
  7.         fillValue(tasks, leastTime);
  8.         Scanner scanner = new Scanner(System.in);
  9.         System.out.println();
  10.         System.out.print("请输入任务个数：");
  11.         int n = scanner.nextInt();
  12.         tasks = new int[n+1][3];
  13.         for (int i = 1; i <= n; i++){
  14.             System.out.print("请输入任务"+i+"起始时间、终止时间、报酬：");
  15.             tasks[i] = new int[]{scanner.nextInt(), scanner.nextInt(), scanner.nextInt()};
  16.         }
  17.         System.out.print("请输入任务的最后终止时间：");
  18.         leastTime = scanner.nextInt();
  19.         fillValue(tasks, leastTime);
  20.     }
  21.     /**
  22.      * 动态规划填充表格并逆推出路径
  23.      * @param tasks tasks[1...n][0...2]代表n个任务的起始时间、终止时间、报酬
  24.      * @param lastTime 任务的最后终止时间
  25.      */
  26.     public static int[] fillValue(int[][] tasks, int lastTime) {
  27.         // 动态规划表格
  28.         int[][] maxValue = new int[tasks.length][lastTime + 1];
  29.         for (int i = 1; i <= tasks.length-1 ; i++) {
  30.             for (int j = 1; j <= lastTime ; j++) {
  31.                 if (j < tasks[i][1]) {
  32.                     // 第i个任务的结束时间未到，不可安排
  33.                     maxValue[i][j] = maxValue[i - 1][j];
  34.                 } else {
  35.                     // 任务可选时有两种选择，即选择当前物品与不选择当前物品
  36.                     maxValue[i][j] = Math.max(maxValue[i-1][j], tasks[i][2]+maxValue[i-1][tasks[i][0]]);
  37.                 }
  38.             }
  39.         }
  40.         System.out.println("总报酬："+maxValue[tasks.length-1][lastTime]);
  41.         // 逆推出路径
  42.         int nowTime = lastTime;
  43.         int[] choose = new int[tasks.length];
  44.         for (int i = tasks.length-1; i > 0; i--){
  45.             if (maxValue[i][nowTime] == maxValue[i-1][nowTime]){
  46.                 // 没有选择第i个任务
  47.                 choose[i] = 0;
  48.             } else {
  49.                 // 选择了第i个任务
  50.                 choose[i] = 1;
  51.                 nowTime = tasks[i][0];
  52.             }
  53.         }
  54.         System.out.print("安排：");
  55.         for (int i = 1; i < choose.length; i++){
  56.             System.out.print(choose[i] + " ");
  57.         }
  58.         System.out.println();
  59.         return choose;
  60.     }
  61. }