司机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);}// index.....所有的司机,往A和B区域分配!// A区域还有rest个名额!// 返回把index...司机,分配完,并且最终A和B区域同样多的情况下,index...这些司机,整体收入最大是多少!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);}// index.....所有的司机,往A和B区域分配!// A区域还有rest个名额!// 返回把index...司机,分配完,并且最终A和B区域同样多的情况下,index...这些司机,整体收入最大是多少!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);}// index.....所有的司机,往A和B区域分配!// A区域还有rest个名额!// 返回把index...司机,分配完,并且最终A和B区域同样多的情况下,index...这些司机,整体收入最大是多少!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("测试结束");}
}
更多推荐
现有司机N*2人,调度中心会将所有司机平分给A、B两个区域,第 i 个司机去A可得收入
发布评论