暴力递归

分析题干：

1：将arr数组分成两个集合，并且两个集合的累加和尽量的接近。

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

那就假设arr数组中元素的累加和是sum，让两个集合的累加和都接近sum / 2，自然两个集合的累加和就接近了。

在两个集合都接近sum / 2时，可能会出现一个超过sum / 2一点，另一个小于sum / 2一点，因为返回最接近情况下的最小集合累

加和。所以就返回小于sum / 2一点的这个就好。

所以递归的时候我们找累加和小于sum / 2一点的返回。这也就是

	if (arr[index] <= rest) { //    ---注意---
        p2 = arr[index] + process(arr, index + 1, rest - arr[index]);
     }

这个条件加上的原因。

	public static int right(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //sum -> 累加和
        int sum = 0;
        for (int nub : arr) {
            sum += nub;
        }
        //因为两个集合是二元相对的所以找到一个就相当于找到另一个了。
        int a = process(arr, 0, sum / 2);
        return a;
    }

    //从index = 0位置出发，找到不超过但是最接近rest的累计和，然后返回该累计和。
    //同样这里要求找到不超过但是最接近rest的累加和。同样是二元相对的，找的这个就对应找到另一个。
    public static int process(int[] arr, int index, int rest) {
        if (index == arr.length) {
            return 0;
        }
        //不要index位置
        int p1 = process(arr, index + 1, rest);
        //要index位置
        int p2 = 0;
        if (arr[index] <= rest) { //    ---注意---
            p2 = arr[index] + process(arr, index + 1, rest - arr[index]);
        }
        return Math.max(p1, p2);
    }

dp方法

public static int dp(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    //sum -> 累加和
    int sum = 0;
    for (int nub : arr) {
        sum += nub;
    }
    int N = arr.length;
    int rest = sum / 2;
    int[][] dp = new int[N + 1][rest + 1];
    for (int i = 0; i <= rest; i++) {
        dp[N][i] = 0;
    }
    for (int H = N - 1; H >= 0; H--) {
        for (int L = 0; L <= rest; L++) {
            //不要index位置
            int p1 = dp[H + 1][L];
            //要index位置
            int p2 = 0;
            if (arr[H] <= L) {
                p2 = arr[H] + dp[H + 1][L - arr[H]];
            }
            dp[H][L] = Math.max(p1, p2);
        }
    }
    return dp[0][rest];
}

526互联

两个集合最接近的累加和

暴力递归

dp方法