2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个集合的累加和接近,返回最接近的情况下,较小集合的累加和。
福哥答案2020-02-25:
自然智慧即可。
1.递归。有代码。
2.动态规划。dp是三维数组。有代码。
代码用golang编写,代码如下:
package main import "fmt" const INT_MAX = int(^uint(0) >> 1) const INT_MIN = ^INT_MAX func main() { arr := []int{1, 2, 3, 4, 100} ret := right1(arr) fmt.Println("1.递归:", ret) ret = right2(arr) fmt.Println("2.动态规划:", ret) } func right1(arr []int) int { if len(arr) < 2 { return 0 } sum := 0 for _, v := range arr { sum += v } if len(arr)&1 == 0 { return process1(arr, 0, len(arr)/2, sum/2) } else { ret1 := process1(arr, 0, len(arr)/2, sum/2) ret2 := process1(arr, 0, len(arr)/2+1, sum/2) if ret1 < ret2 { return ret2 } else { return ret1 } } } func process1(arr []int, i int, picks int, rest int) int { if i == len(arr) { if picks == 0 { return 0 } else { return -1 } } else { p1 := process1(arr, i+1, picks, rest) p2 := -1 next := -1 if arr[i] <= rest { next = process1(arr, i+1, picks-1, rest-arr[i]) } if next != -1 { p2 = arr[i] + next } return GetMax(p1, p2) } } func right2(arr []int) int { if len(arr) < 2 { return 0 } sum := 0 for _, v := range arr { sum += v } sum >>= 1 N := len(arr) M := (len(arr) + 1) >> 1 dp := make([][][]int, N) for i := 0; i < N; i++ { dp[i] = make([][]int, M+1) for j := 0; j < M+1; j++ { dp[i][j] = make([]int, sum+1) for k := 0; k < sum+1; k++ { dp[i][j][k] = INT_MIN } } } for i := 0; i < N; i++ { for k := 0; k <= sum; k++ { dp[i][0][k] = 0 } } for k := 0; k <= sum; k++ { if arr[0] <= k { dp[0][1][k] = arr[0] } else { dp[0][1][k] = INT_MIN } } for i := 1; i < N; i++ { for j := 1; j <= GetMin(i+1, M); j++ { for k := 0; k <= sum; k++ { dp[i][j][k] = dp[i-1][j][k] if k-arr[i] >= 0 { dp[i][j][k] = GetMax(dp[i][j][k], dp[i-1][j-1][k-arr[i]]+arr[i]) } } } } return GetMax(dp[N-1][M][sum], dp[N-1][N-M][sum]) } func GetMin(a int, b int) int { if a < b { return a } else { return b } } func GetMax(a int, b int) int { if a > b { return a } else { return b } }
执行结果如下: