动态规划-规划兼职工作

一、问题描述

你打算利用空闲时间来做兼职工作赚些零花钱。这里有 n 份兼职工作，每份工作预计从 startTime 开始到 endTime 结束，报酬为 profit。给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。

注意：

• 时间上出现重叠的 2 份工作不能同时进行。

• 如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。

二、问题分析

例如现在输入一组数据：

• startTime = [1,2,3,3]

• endTime = [3,4,5,6]

• profit = [50,10,40,70]

表示兼职表有4份工作：

工作1：开始时间：1，结束时间：3，薪资：50

工作2：开始时间：2，结束时间：4，薪资：10

工作3：开始时间：3，结束时间：5，薪资：40

工作4：开始时间：3，结束时间：6，薪资：70

第一步：找出最优解的性质，并刻画其结构特征。

简单尝试穷举法：

方案1：工作1或工作2=50或10

方案2：工作1+工作3=50+40=90

方案3：工作1+工作4=50+70=120

…

发现问题：组合很多，由于有起始时间和结束时间导致没有很好的排序组合方案

三、动态规划方程，即递归关系

第二步：递归定义最优值

• dp[i] 表示前i份兼职工作可以获得的最大报酬。
• k 表示满足结束时间小于等于第i−1 份工作开始时间的兼职工作数量。
• profit[i−1]表示第i份工作的薪酬。
• 该公式表示：完成第i份兼职获得的最大报酬=MAX(考虑前一份（i-1）兼职的最大报酬,第i份兼职开始时间前能完成的兼职的最大报酬+第i份兼职的报酬)。

四、代码分析

第三步：自底向上的方式计算最值

1.基本代码和解释

public static int jobScheduling(int[] startTime, int[] endTime, int[] profit, int[] dp, String[] optimal) {// 工作数量int n = startTime.length;// 存储工作的int[][] jobs = new int[n][];// 放入for (int i = 0; i < n; i++) {jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};}// 按结束时间排序Arrays.sort(jobs, Comparator.comparingInt(a -> a[1]));// 对每份工作判断for (int i = 1; i <= n; i++) {// 查找合适的工作// k 表示满足结束时间小于等于第i−1份工作开始时间的兼职工作数量int k = binarySearch(jobs, i - 1, jobs[i - 1][0]);// dp[i]=max(dp[i−1],dp[k]+profit[i−1])// 每份工作薪资和(前一份工作薪资，当前工作开始时间前可以结束的工作薪资+当前工作薪资)dp[i] = Math.max(dp[i - 1], dp[k] + jobs[i - 1][2]);//判断是否选择了i兼职if (dp[i] == dp[i - 1]) {// 如果未选择，表示i-1前是最优解optimal[i] = optimal[i - 1];} else {// 如果选择表示：最优解=i开开始前最优解+ioptimal[i] = (optimal[k] + " " + String.valueOf(i)).trim();}}return dp[n];
}
public static int binarySearch(int[][] jobs, int right, int target) {int left = 0;while (left < right) {int mid = left + (right - left) / 2;if (jobs[mid][1] > target) {right = mid;} else {left = mid + 1;}}return left;}

2.测试

public static void main(String[] args) {// 开始时间int[] startTime = {1, 2, 3, 3};// 结束时间int[] endTime = {3, 4, 5, 6};// 薪资表int[] profit = {50, 10, 40, 70};// 报酬数组int[] dp = new int[startTime.length + 1];// 最优解数组String[] optimal = new String[startTime.length + 1];optimal[0] = " ";int i = jobScheduling(startTime, endTime, profit, dp, optimal);System.out.println("共获得报酬=" + i);System.out.println("工作和薪酬关系=" + Arrays.toString(dp));System.out.println("最优兼职表=" + Arrays.toString(optimal));
}

共获得报酬=120
工作和薪酬关系=[0, 50, 50, 90, 120]
最优兼职表=[ , 1, 1, 1 3, 1 4]

问题总结

在这道动态规划案例中：

• 要点

  完成第i份兼职获得的最大报酬=MAX(考虑前一份（i-1）兼职的最大报酬,第i份兼职开始时间前能完成的兼职的最大报酬+第i份兼职的报酬)。
  在计算时考虑当前兼职时，要用到之前子问题的解时，我们直接查兼职与最大薪资表dp就可以简化运算。

• 算法性能分析

  • 时间复杂度：O(nlogn)，其中 n 是兼职工作的数量。排序需要 O(nlogn)，遍历 + 二分查找需要 O(nlogn)，因此总时间复杂度为 O(nlogn)。
  • **空间复杂度：O(n)。**需要 O(n) 的空间来保存dp。

• 现实意义

  通过学习动态规划，弄懂该案例，不光可以学习如何兼职获取最大收益，也能用在其他和时间有关的规划问题中，

  设计动态规划算法的步骤

  （1）找出最优解的性质，并刻画其结构特性。

  （2）递归地定义最优值。

  （3）以自底向上的方式计算最优值

  （4）根据计算最优值时得到的信息，构建最优解。