2021-02-25：給定一個(gè)正數(shù)數(shù)組arr什燕，請(qǐng)把a(bǔ)rr中所有的數(shù)分成兩個(gè)集合粘勒。如果arr長(zhǎng)度為偶數(shù)，兩個(gè)集合包含數(shù)的個(gè)數(shù)要一樣多屎即；如果arr長(zhǎng)度為奇數(shù)庙睡，兩個(gè)集合包含數(shù)的個(gè)數(shù)必須只差一個(gè)。請(qǐng)盡量讓兩個(gè)集合的累加和接近技俐，返回最接近的情況下乘陪，較小集合的累加和。
福哥答案2020-02-25：
自然智慧即可虽另。
1.遞歸暂刘。有代碼。
2.動(dòng)態(tài)規(guī)劃捂刺。dp是三維數(shù)組谣拣。有代碼。
代碼用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.動(dòng)態(tài)規(guī)劃：", 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
}
}
執(zhí)行結(jié)果如下：
在這里插入圖片描述
