动态规划：较小集合的累加和 + 限制集合中数字的个数

1、题目

给定一个正数数组 arr，请把 arr 中所有的数分成两个集合。

如果 arr 长度为偶数，两个集合包含数的个数要一样多；如果 arr 长度为奇数，两个集合包含数的个数必须只差一个。

请尽量让两个集合的累加和接近。

返回最接近的情况下，较小集合的累加和。

2、思路

本题为 2021 字节跳动北美原题。

两个限制：个数 和 累加和

• 偶数的情况：例有 8 个数，所有数的累加和为100，则应该是必须选择 4 个数，使得其累加和 <= 50；
• 奇数的情况：例有 7 个数，所有数的累加和为100，就分两种情况：
  • ①必须选择 3 个数的情况，使其累加和 <= 50；
  • ②必须选择 4 个数的情况，使其累加和 <= 50。
  • 选择 ①② 中最接近 50 的。

2.1 暴力递归版本

public class SplitSumClosedSizeHalf {
    public static int right(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0; //统计所有数的累加和
        for (int num : arr) {
            sum += num;
        }
        
        if ((arr.length & 1) == 0) { //arr长度为偶数
            return process(arr, 0, arr.length / 2, sum / 2);
        } else { // arr长度为奇数
            return Math.max(process(arr, 0, arr.length / 2, sum / 2), process(arr, 0, arr.length / 2 + 1, sum / 2));
        }
    }
    
    //arr从i位置往后自由选择，挑选的个数一定要是picks个，累计和<=rest，但是最接近rest的那个结果返回
    public static int process(int[] arr, int i, int picks, int rest) {
        
        if (i == arr.length) {
            //没数了且挑的个数也是0个的时候才是有效解
            return picks == 0 ？ 0 : -1;
        } else {
            int p1 = process(arr, i + 1, picks, rest); //不要i位置的数
            
            //就是要用arr[i] 的数
            int p2 = -1;
            int next = -1;
            if (arr[i] <= rest) {
                next = process(arr, i + 1, picks - 1, rest - arr[i]);
            }
            if (next != -1) { //有效解
                p2 = arr[i] + next;
            }
            
            return Math.max(p1, p2);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

递归函数中有 3 个可变参数，所以准备一个三维表。

2.2 动态规划版本

public class SplitSumClosedSizeHalf {
	public static int dpWay(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0; //统计所有数的累加和
        for (int num : arr) {
            sum += num;
        }
        sum /= 2;
        
        int n = arr.length;
        int m = (n + 1) / 2;
        //注意picks的范围是 "n/2 向上取整" = (n + 1) / 2
        int[][][] dp = new int[n + 1][m + 1][sum + 1];
        
        //三维表
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= sum; k++) {
                    dp[i][j][k] = -1; //所有位置在计算之前都是无效的
                }
            }
        }
        
        //base case
        for (int rest = 0; rest <= sum; rest++) {
            dp[n][0][rest] = 0; //第n层已经填好
        }
        
        //i为三维的层
        for (int i = n - 1; i >= 0; i--) { //层数倒着填
            for (int picks = 0; picks <= m; picks++) { //另外两维从左往右或是从右往左填都可以
                for (int rest = 0; rest <= sum; rest++) {
                    int p1 = dp[i + 1][picks][rest];
                    int p2 = -1;
                    int next = -1;
                    if (picks - 1 >= 0 && arr[i] <= rest) {
                        next = dp[i + 1][picks - 1][rest - arr[i]];
                    }
                    if (next != -1) { //有效解
                        p2 = arr[i] + next;
                    }
            
            		dp[i][picks][rest] = Math.max(p1, p2);
                }
            }
        }
        
        if ((n & 1) == 0) {
            return dp[0][n / 2][sum];
        } else { // arr长度为奇数
            return Math.max(dp[0][n/2][sum], dp[0][n / 2 + 1][sum]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56