暴力递归转动态规划（十六）

递归转动态规划（十六）"/>

暴力递归转动态规划（十六）

题目
给定一个正数数组arr，
请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近
返回：最接近的情况下，较小集合的累加和。
注：只要求两个集合的累加和最接近情况下较小的一个，不要求两个集合个数相同或相近。

暴力递归
这道题其实和之前说过的背包问题是一样的逻辑。
让两个集合的累加和相近的方法就是求出老数组累加和的一半。并在遍历数组的过程中以此条件作为基准，如果加上当前数后，累加和大于数组一半的值，那这个数就舍弃不要。否则就加上这个数。继续向下递归。

代码
因为求的是所有数的累加和 小于 老数组的一半，所以要取Math.max(p1,p2)。目的是找出最接近老数组一半的累加和。

 public static int right(int[] arr) {if (arr == null || arr.length < 2) {return 0;}int sum = 0;for (int i = 0; i < arr.length; i++) {sum += arr[i];}return process(arr, 0, sum / 2);}public static int process(int[] arr, int index, int rest) {if (index == arr.length) {return 0;} else {//背包问题，这个数可能要，也可能不要int p1 = process(arr, index + 1, rest);//这个数如果要，就不能大于剩余数值int p2 = 0;if (arr[index] <= rest) {p2 = arr[index] + process(arr, index + 1, rest - arr[index]);}return Math.max(p1, p2);}}

动态规划
写出了尝试的暴力递归方法后，动态规划方法就相对简单。

1. 根据暴力递归方法中的可变参数来确定dp表的范围（index可到达arr.length ， rest可到达 0 ）。
2. 根据暴力递归方法中base case来填充dp表默认值（这道题中是 index = arr.length，return 0），而int[] 创建后，每个格子的初始化默认值就是0，所以不用额外处理。
3. 根据暴力递归代码中的依赖关系写循环，无论当前值要不要 index都 + 1，如果要p2,则rest - arr[index]。 所以可以确定 index是依赖关系是从尾端到0（arr.length ~ 0），而rest依赖是从 0 ~ arr的累加和 / 2。
   所以填充index要从arr.length 向 0遍历，rest从0 向 arr遍历。
   因为这道题在填充dp表的每个格子时没有枚举行为（for循环），所以到这步就可以了。

代码

 public static int dp(int[] arr) {if (arr == null || arr.length < 2) {return 0;}int sum = 0;for (int i = 0; i < arr.length; i++) {sum += arr[i];}int N = arr.length;int M = sum / 2;int[][] dp = new int[N + 1][M + 1];for (int index = N - 1; index >= 0; index--) {for (int rest = 0; rest <= M; rest++) {int p1 = dp[index + 1][rest];//这个数如果要，就不能大于剩余数值int p2 = 0;if (arr[index] <= rest) {p2 = arr[index] + dp[index + 1][rest - arr[index]];}dp[index][rest] = Math.max(p1, p2);}}return dp[0][M];}