2021-06-22：现有司机N*2人，调度中心会将所有司机平分给A、B两个区域

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

福大大 答案2021-06-22：

自然智慧。递归或者动态规划，代码里有贪心策略。

只能去A。只能去B。A和B都能去。总共只有这三种情况。

代码用golang编写。代码如下：

```go

package main

import (

"fmt"

"sort"

)

func main() {

income := [][]int{{1, 2, 3, 4, 5, 6}, {7, 8, 9, 10, 11, 12}}

ret1 := maxMoney1(income)

fmt.Println(ret1)

ret3 := maxMoney3(income)

fmt.Println(ret3)

}

// 这题有贪心策略 :

// 假设一共有10个司机，思路是先让所有司机去A，得到一个总收益

// 然后看看哪5个司机改换门庭(去B)，可以获得最大的额外收益

// 这道题有贪心策略，打了我的脸

// 但是我课上提到的技巧请大家重视

// 根据数据量猜解法可以省去大量的多余分析，节省时间

// 这里感谢卢圣文同学

func maxMoney3(income [][]int) int {

N := len(income)

arr := make([]int, N)

sum := 0

for i := 0; i < N; i++ {

arr[i] = income[i][1] - income[i][0]

sum += income[i][0]

}

sort.Slice(arr, func(i, j int) bool {

return arr[i] <= arr[j]

})

M := N >> 1

for i := N - 1; i >= M; i-- {

sum += arr[i]

}

return sum

}

// 课上的现场版本

// income -> N * 2 的矩阵 N是偶数！

// 0 [9, 13]

// 1 [45,60]

func maxMoney1(income [][]int) int {

if len(income) < 2 || (len(income)&1) != 0 {

return 0

}

N := len(income) // 司机数量一定是偶数，所以才能平分，A N /2 B N/2

M := N >> 1 // M = N / 2 要去A区域的人

return process1(income, 0, M)

}

// index.....所有的司机，往A和B区域分配！

// A区域还有rest个名额!

// 返回把index...司机，分配完，并且最终A和B区域同样多的情况下，index...这些司机，整体收入最大是多少！

func process1(income [][]int, index int, rest int) int {

if index == len(income) {

return 0

}

// 还剩下司机！

if len(income)-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，或者去B

p1 := income[index][0] + process1(income, index+1, rest-1)

p2 := income[index][1] + process1(income, index+1, rest)

return getMax(p1, p2)

}

func getMax(a int, b int) int {

if a > b {

return a

} else {

return b

}

}

```

执行结果如下：

***

[左神java代码]( https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class02/Code04_Drive.java)