现有司机N*2人，调度中心会将所有司机平分给A、B两个区域，第 i 个司机去A可得收入

现有司机N*2人，调度中心会将所有司机平分给A、B两个区域，第 i 个司机去A可得收入

目录

• • 题目描述
  • 举例描述
  • 暴力递归
  • 暴力递归改进版
  • 动态规划
  • 贪心策略
  • 对数器测试

题目描述

现有司机 N * 2 人，调度中心会将所有司机平分给 A、B 两个区域
第 i 个司机去 A 可得收入为 income[i][0],
第 i 个司机去 B 可得收入为 income[i][1],
返回所有调度方案中能使所有司机总收入最高的方案，是多少钱

题目的意思不难理解，就是有偶数个司机，告诉你每个司机去 A 和去 B 分别能够获得多少钱，需要将所有司机平分到 A 和 B 区域，需要求出总收入最高的司机调度方案中获得的总收入

举例描述

比如现在有 4 个司机，income数组如下:

  [10, 13][23, 17][18, 22][42, 56]

因为一共有 4 个司机，所以平分后应当是去 A 的有两个司机，去 B 的有两个司机，那么谁去 A 谁去 B 才能获得最高的总收入，这个总收入是多少呢？这个就是这道题要我们求的结果

• 让 0 号司机去 A
• 让 1 号司机去 A
• 让 2 号司机去 B
• 让 3 号司机去 B

这样得到的总收入是10 + 23 + 22 + 56 === 111是最高收入

暴力递归

    public static int maxMoney2(int[][] income){if (income == null || income.length < 2 || (income.length % 2)!=0){return 0;}int N = income.length;int M = N >> 1;return process2(income,0,M,M);}// 所有的司机，往A和B区域分配！// A区域还有rest个名额!// 返回把司机，分配完，并且最终A和B区域同样多的情况下&#这些司机，整体收入最大是多少！private static int process2(int[][] income, int index, int restA,int restB) {//越界了if (index == income.length){return 0;}if (restA == 0){return income[index][1] + process2(income, index + 1, restA,restB-1);}if (restB == 0){return income[index][0] + process2(income,index+1,restA-1,restB);}// 当前司机，可以去A，或者去Bint p1 = income[index][0] + process2(income, index + 1,restA-1, restB);int p2 = income[index][1] + process2(income, index + 1, restA,restB-1);return Math.max(p1, p2);}

暴力递归改进版

  public static int maxMoney1(int[][] income){if (income == null || income.length < 2 || (income.length % 2)!=0){return 0;}int N = income.length;int M = N >> 1;return process1(income,0,M);}// 所有的司机，往A和B区域分配！// A区域还有rest个名额!// 返回把司机，分配完，并且最终A和B区域同样多的情况下&#这些司机，整体收入最大是多少！private static int process1(int[][] income, int index, int rest) {//越界了if (index == income.length) {return 0;}// 还剩下司机！//还剩下两个司机 ,A还有2个名额  只能往A里面放if (income.length - index == rest) {return income[index][0] + process1(income, index + 1, rest - 1);}if (rest == 0) {return income[index][1] + process1(income, index + 1, rest);}// 当前司机，可以去A，或者去Bint p1 = income[index][0] + process1(income, index + 1, rest - 1);int p2 = income[index][1] + process1(income, index + 1, rest);return Math.max(p1, p2);}

动态规划

    public static int maxMoney2(int[][] income){if (income == null || income.length < 2 || (income.length % 2)!=0){return 0;}int N = income.length;int M = N >> 1;int[][] dp = new int[N + 1][M + 1];for (int i = N - 1; i >= 0; i--){for (int j = 0; j <=M; j++) {if (N-i==j){dp[i][j] = income[i][0] +dp[i + 1][j - 1];}else if (j == 0){dp[i][j] = income[i][1] +dp[i + 1][j];}else {int p1 = income[i][0] + dp[i + 1][j - 1];int p2 = income[i][1] + dp[i + 1][j];dp[i][j] = Math.max(p1, p2);}}}return dp[0][M];}

贪心策略

假设一共有10个司机，思路是先让所有司机去A，得到一个总收益
然后看看哪5个司机改换门庭(去B)，可以获得最大的额外收益

 public static int maxMoney3(int[][] income) {int N = income.length;int[] arr = new int[N];int sum = 0;for (int i = 0; i < N; i++) {arr[i] = income[i][1] - income[i][0];sum += income[i][0];}Arrays.sort(arr);int M = N >> 1;for (int i = N - 1; i >= M; i--) {sum += arr[i];}return sum;}

对数器测试

public class Drive {public static int maxMoney1(int[][] income){if (income == null || income.length < 2 || (income.length % 2)!=0){return 0;}int N = income.length;int M = N >> 1;return process1(income,0,M);}// 所有的司机，往A和B区域分配！// A区域还有rest个名额!// 返回把司机，分配完，并且最终A和B区域同样多的情况下&#这些司机，整体收入最大是多少！private static int process1(int[][] income, int index, int rest) {//越界了if (index == income.length) {return 0;}// 还剩下司机！//还剩下两个司机 ,A还有2个名额  只能往A里面放if (income.length - index == rest) {return income[index][0] + process1(income, index + 1, rest - 1);}if (rest == 0) {return income[index][1] + process1(income, index + 1, rest);}// 当前司机，可以去A，或者去Bint p1 = income[index][0] + process1(income, index + 1, rest - 1);int p2 = income[index][1] + process1(income, index + 1, rest);return Math.max(p1, p2);}public static int maxMoney2(int[][] income){if (income == null || income.length < 2 || (income.length % 2)!=0){return 0;}int N = income.length;int M = N >> 1;int[][] dp = new int[N + 1][M + 1];for (int i = N - 1; i >= 0; i--){for (int j = 0; j <=M; j++) {if (N-i==j){dp[i][j] = income[i][0] +dp[i + 1][j - 1];}else if (j == 0){dp[i][j] = income[i][1] +dp[i + 1][j];}else {int p1 = income[i][0] + dp[i + 1][j - 1];int p2 = income[i][1] + dp[i + 1][j];dp[i][j] = Math.max(p1, p2);}}}return dp[0][M];}// 返回随机len*2大小的正数矩阵// 值在0~value-1之间public static int[][] randomMatrix(int len, int value) {int[][] ans = new int[len << 1][2];for (int i = 0; i < ans.length; i++) {ans[i][0] = (int) (Math.random() * value);ans[i][1] = (int) (Math.random() * value);}return ans;}// 这题有贪心策略 :// 假设一共有10个司机，思路是先让所有司机去A，得到一个总收益// 然后看看哪5个司机改换门庭(去B)，可以获得最大的额外收益public static int maxMoney3(int[][] income) {int N = income.length;int[] arr = new int[N];int sum = 0;for (int i = 0; i < N; i++) {arr[i] = income[i][1] - income[i][0];sum += income[i][0];}Arrays.sort(arr);int M = N >> 1;for (int i = N - 1; i >= M; i--) {sum += arr[i];}return sum;}public static void main(String[] args) {int N = 10;int value = 100;int testTime = 500;System.out.println("测试开始");for (int i = 0; i < testTime; i++) {int len = (int) (Math.random() * N) + 1;int[][] matrix = randomMatrix(len, value);int ans1 = maxMoney1(matrix);int ans2 = maxMoney2(matrix);int ans3 = maxMoney3(matrix);if (ans1 != ans2 || ans1 != ans3) {System.out.println(ans1);System.out.println(ans2);System.out.println(ans3);System.out.println("Oops!");}}System.out.println("测试结束");}
}