【算法&数据结构体系篇class23】：暴力递归到动态规划

￡神魔★判官ぃ 2024-03-24 15:40 37阅读 0赞

### 题目一、 ###

### 给定一个正数数组arr， ###

### 请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近 ###

### 返回： ###

### 最接近的情况下，较小集合的累加和 ###

package class23;
    
    /**
     * 给定一个正数数组arr，
     * 请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近
     * 返回：
     * 最接近的情况下，较小集合的累加和
     */
    public class SplitSumClosed {
    
        //方法一：暴力递归
        public static int right(int[] arr){
            //边界判断 少于2个 就不符合题意
            if(arr ==  null || arr.length < 2) return 0;
    
            //需要分成两个集合，且累加和接近 那么就可以判断一个边界范围 是不超过全部数和的一半
            int sum = 0;
            for(int a:arr){
                sum += a;
            }
    
            //调用递归函数 从数组0开始，到sum/2;
            return process(arr, 0, sum/2);
        }
    
        /**
         * 对数组[index...]的数据划分靠近rest当前剩余累加和数，且不超过rest 返回该最接近且不超过rest的累加和
         * @param arr
         * @param index
         * @param rest
         * @return
         */
        public static int process(int[] arr, int index, int rest){
            //base case: 当前来到越界数组 没有元素了 那么就表示到底 直接返回0
            if(index == arr.length) return  0;
    
            //不越界 表示还有数，那么就分析情况，取该数与不取两种情况
            //1.当前index 不累加 那么就返回 下一个位置 index+1 位置   rest不需要减，因为没有选择就不影响
            int p1 = process(arr,index+1,rest);
    
            //2.当前index 累加，需要先判断是否越界 就是当前剩余数rest 减完arr[index]值要大于等于0 因为我们要求的是较小集合
            int p2 = 0;
            if(arr[index] <= rest){
                p2 = process(arr, index+1,rest-arr[index]);
            }
            return Math.max(p1,p2);    //两者情况都是符合接近且较小的 但是要取更接近那肯定是较大的更接近中间值的
        }
    
    
        //方法二：动态规划
        public static int dp(int[] arr){
            if(arr == null || arr.length < 2) return 0;
    
            //分析递归可变参数 index  范围0-arr.length   rest 范围0-sum/2
            int n = arr.length;
            int sum = 0;
            for(int num:arr){
                sum+=num;
            }
            //求和接近 所以是总和一半
            sum /= 2;
            int[][] dp = new int[n+1][sum+1];
            //base case 越界index == arr.length 返回0 初始化即为0 不需要处理 完成dp[n] 最后一行的赋值
            //分析依赖 index 依赖 index+1 也就是上一行依赖下一行 所以从倒数第二行开始往上赋值
            for(int index = n-1;index>=0;index--){
                for(int rest = 0; rest <= sum ; rest++){
    
                //不越界 表示还有数，那么就分析情况，取该数与不取两种情况
                //1.当前index 不累加 那么就返回 下一个位置 index+1 位置   rest不需要减，因为没有选择就不影响
                int p1 = dp[index+1][rest];
    
                //2.当前index 累加，需要先判断是否越界 就是当前剩余数rest 减完arr[index]值要大于等于0 因为我们要求的是较小集合
                int p2 = 0;
                if(arr[index] <= rest){
                    p2 = dp[index+1][rest-arr[index]];
                }
                dp[index][rest] = Math.max(p1,p2);    //两者情况都是符合接近且较小的 但是要取更接近那肯定是较大的更接近中间值的
                }
            }
            return dp[0][sum/2];     //最后返回递归调用的主函数的位置 0位置开始 在总数一半的位置
        }
    
        public static int[] randomArray(int len, int value) {
            int[] arr = new int[len];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) (Math.random() * value);
            }
            return arr;
        }
    
        public static void printArray(int[] arr) {
            for (int num : arr) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            int maxLen = 20;
            int maxValue = 50;
            int testTime = 10000;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int len = (int) (Math.random() * maxLen);
                int[] arr = randomArray(len, maxValue);
                int ans1 = right(arr);
                int ans2 = dp(arr);
                if (ans1 != ans2) {
                    printArray(arr);
                    System.out.println(ans1);
                    System.out.println(ans2);
                    System.out.println("Oops!");
                    break;
                }
            }
            System.out.println("测试结束");
        }
    
    }

### 题目二 ###

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

### 如果arr长度为偶数，两个集合包含数的个数要一样多 ###

### 如果arr长度为奇数，两个集合包含数的个数必须只差一个 ###

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

### 返回： ###

### 最接近的情况下，较小集合的累加和 ###

package class23;
    
    /**
     * 给定一个正数数组arr，请把arr中所有的数分成两个集合
     * 如果arr长度为偶数，两个集合包含数的个数要一样多
     * 如果arr长度为奇数，两个集合包含数的个数必须只差一个
     * 请尽量让两个集合的累加和接近
     * 返回：
     * 最接近的情况下，较小集合的累加和
     */
    public class SplitSumClosedSizeHalf {
    
        //方法一：暴力递归
        public static int right(int[] arr){
            //边界判断
            if(arr == null || arr.length <2) return 0;
    
            //分成两个集合累加和接近 所以就要取总数一半作为一个条件递归 /2
            int sum = 0;
            for(int num:arr){
                sum += num;
            }
            sum /= 2;
            //注意这里 如果偶数个，那么两个集合个数一样多 奇数个 只能相差一个 比如6->> 3,3 (6/2=3)   7->>3,4  (7/2 +1 =4)
            //返回接近情况下 较小集合的一个
            // 偶数个情况下 个数都一样arr.length/2   奇数个情况下 个数不一样arr.length/2 arr.length/2 +1 两种情况需要比较取较大者
    
            if((arr.length & 1) == 0){
                //长度 与运算1 为0  表示地位是0  即为偶数  所以集合长度pick一样  sum为总和一半
                return process(arr, 0, arr.length/2, sum);
            }else {
                //否则就是奇数  两个集合数量就是 n  n+1 相差一个 分别进行递归取其一较大值 更接近中间值
                return Math.max(process(arr,0, arr.length/2, sum), process(arr, 0, arr.length/2 +1, sum));
            }
        }
    
        /**
         * // arr[i....]自由选择，挑选的个数一定要是pick个，累加和<=rest, 离rest最近的返回
         * @param arr
         * @param index
         * @param pick
         * @param rest
         * @return
         */
        public static int process(int[] arr, int index, int pick, int rest){
            //base case:数组越界 没有元素可选了 且挑选pick个数为0 那么就是表示不需要再取了。返回0  否则就要返回-1表示无效
            if(index == arr.length){
                return pick == 0 ? 0 : -1;
            }else {
                //没有越界 就分析情况 当前位置选与不选
                int p1 = process(arr,index+1, pick, rest);
    
                int p2 = -1;
                int next = -1;
                if(arr[index] <= rest){
                    //只有该位置值小于等于 目前剩余的目标值 才能有next
                    next = process(arr,index+1, pick-1, rest-arr[index]);
                }
                if(next != -1){
                    //如果index+1后面的累加值有符合情况 再刷新p2 将当前arr[index]加上
                    p2 = arr[index] + next;
                }
                return Math.max(p1,p2);  //两种情况返回较大值，更接近总数一半的情况
            }
        }
    
        //方法二：动态规划
        public static int dp(int[] arr){
            if(arr == null || arr.length < 2) return 0;
    
            //分析可变参数
            // 索引index 0-arr.length  可挑个数 pick 0-arr.length/2+1  总数一半目标值 rest 0-arr.length/2
            int n = arr.length;
            int m = arr.length/2 + 1;
            int sum = 0;
            for(int num:arr){
                sum+=num;
            }
            //总数一半 两个集合累加接近 取较小 那么就是累加不超过一半
            sum /= 2;
            int[][][] dp = new int[n+1][m+1][sum+1];
            //根据递归设定 我们假设全部是-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:数组越界 没有元素可选了 且挑选pick个数为0 那么就是表示不需要再取了。返回0  否则就要返回-1表示无效
            for(int rest = 0; rest <= sum; rest++){
                dp[n][0][rest] = 0;
            }
    
            //分析依赖 index 依赖于index+1 上一行依赖下一行 已知base case已经来到最后一行 所以从倒数第二行开始往上
            for(int index = n-1; index >= 0; index--){
                for(int pick = 0; pick <= m;pick++){
                    for (int rest = 0; rest <= sum;rest++){
                        //没有越界 就分析情况 当前位置选与不选
                        int p1 = dp[index+1][pick][rest];
    
                        int p2 = -1;
                        int next = -1;
    
                        //注意 pick-1存在越界情况需要判断
                        if(pick-1>=0 && arr[index] <= rest){
                            //只有该位置值小于等于 目前剩余的目标值 才能有next
                            next = dp[index+1][ pick-1][rest-arr[index]];
                        }
                        if(next != -1){
                            p2 = arr[index] + next;
                        }
                        dp[index][pick][rest] = Math.max(p1,p2);  //两种情况返回较大值，更接近总数一半的情况
                    }
                }
            }
    
            //根据递归函数调用 判断数组长度 奇数偶数两种返回值
            if((arr.length & 1) == 0){
                //偶数  第0索引位置 挑取数一半是一样的 接近总数一半
                return dp[0][arr.length/2][sum];
            }else {
                //奇数 就要判断 挑取的奇数和偶数个的较大者 最靠近总数一半的值就是较大的那个
                return Math.max(dp[0][arr.length/2][sum],dp[0][arr.length/2 +1][sum]);
            }
        }
    
        public static int dp2(int[] arr) {
            if (arr == null || arr.length < 2) {
                return 0;
            }
            int sum = 0;
            for (int num : arr) {
                sum += num;
            }
            sum >>= 1;
            int N = arr.length;
            int M = (arr.length + 1) >> 1;
            int[][][] dp = new int[N][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] = Integer.MIN_VALUE;
                    }
                }
            }
            for (int i = 0; i < N; i++) {
                for (int k = 0; k <= sum; k++) {
                    dp[i][0][k] = 0;
                }
            }
            for (int k = 0; k <= sum; k++) {
                dp[0][1][k] = arr[0] <= k ? arr[0] : Integer.MIN_VALUE;
            }
            for (int i = 1; i < N; i++) {
                for (int j = 1; j <= Math.min(i + 1, M); j++) {
                    for (int k = 0; k <= sum; k++) {
                        dp[i][j][k] = dp[i - 1][j][k];
                        if (k - arr[i] >= 0) {
                            dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - 1][k - arr[i]] + arr[i]);
                        }
                    }
                }
            }
            return Math.max(dp[N - 1][M][sum], dp[N - 1][N - M][sum]);
        }
    
        // for test
        public static int[] randomArray(int len, int value) {
            int[] arr = new int[len];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) (Math.random() * value);
            }
            return arr;
        }
    
        // for test
        public static void printArray(int[] arr) {
            for (int num : arr) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
            int maxLen = 10;
            int maxValue = 50;
            int testTime = 10000;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int len = (int) (Math.random() * maxLen);
                int[] arr = randomArray(len, maxValue);
                int ans1 = right(arr);
                int ans2 = dp(arr);
                int ans3 = dp2(arr);
                if (ans1 != ans2 || ans1 != ans3) {
                    printArray(arr);
                    System.out.println(ans1);
                    System.out.println(ans2);
                    System.out.println(ans3);
                    System.out.println("Oops!");
                    break;
                }
            }
            System.out.println("测试结束");
        }
    
    }

### 题目三 ###

### N皇后问题是指在N\*N的棋盘上要摆N个皇后， ###

### 要求任何两个皇后不同行、不同列， 也不在同一条斜线上 ###

###    给定一个整数n，返回n皇后的摆法有多少种。   n=1，返回1 ###

### n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0 ###

### n=8，返回92 ###

注意这道题 没有存在重复解，只能用暴力递归方式解决

package class23;
    
    import java.lang.reflect.Array;
    import java.util.Arrays;
    
    /**
     * N皇后问题是指在N*N的棋盘上要摆N个皇后，
     * 要求任何两个皇后不同行、不同列， 也不在同一条斜线上
     * 给定一个整数n，返回n皇后的摆法有多少种。  n=1，返回1
     * n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0
     * n=8，返回92
     */
    public class NQueens {
        //暴力递归   没有重复解 所以就不能改动态规划
        public static int num1(int n) {
            //边界处理
            if(n < 1) return 0;
    
            //定义一个数组，存放棋盘摆放的位置 n长度的数组 索引表示行 值表示列 减少了空间
            int[] record = new int[n];
            //调用递归 从数组 0 开始 到n结束 递归 判断有多少种符合的摆法
            return process(0,record,n);
        }
    
        /**
         * 	// 当前来到i行，一共是0~N-1行
         * 	// 在i行上放皇后，所有列都尝试
         * 	// 必须要保证跟之前所有的皇后不打架
         * 	// int[] record record[x] = y 之前的第x行的皇后，放在了y列上
         * 	// 返回：不关心i以上发生了什么，i.... 后续有多少合法的方法数
         * @param i
         * @param record
         * @param n
         * @return
         */
        public static int process(int i, int[] record, int n){
            //base case:如果从第0行到n-1行都满足条件 且i当前行已经越界来到n 说明该方法符合返回1
            if(i == n) {
                //符合一种方法后 输出每一行的位置
                System.out.println(Arrays.toString(record));
                return 1;
            }
    
            //还有行需要放置棋盘 分析
            int res = 0;   //定义返回的方法数
            //所在行i都将每一列都遍历一遍
            for(int j = 0; j < n; j++){
                //每一列都需要判断 前面0...i-1行是否符合的 不再同一列 不在同一斜线
                if(isValid(record,i,j)){
                    //都符合 那么说明当前列col可以放皇后
                    record[i] = j;   //第i行放皇后在第col列
                    res += process(i+1,record,n);  //方法值累加 递归到下一行i+1
                }
    
    
            }
    
            return res;   //最后返回方法数
        }
    
        //判断当前第i行j列位置是否可以放皇后
        public static boolean isValid(int[] record,int i, int j){
            // 已知前面0---i-1行都正确放好 所以需要判断是否跟前面0---i-1这么多行的皇后会不会有冲突
            //在同一列     或者在同一对角线
            for(int k = 0; k < i; k++){
                //k行索引对应的值就是所在列record[k] 是否跟当前位置j列同列
                //同一斜线 有个规律，就是每一行的位置 k行,record[k]列 与当前行 i ,j列 行的差和列的差是否相等 相等就是在同一斜线上 就不符合
                if(record[k] == j || Math.abs(record[k]-j) == Math.abs(k - i)){
                    return false;
                }
            }
            return true;
        }
    
        // 请不要超过32皇后问题
        public static int num2(int n) {
            if (n < 1 || n > 32) {
                return 0;
            }
            // 如果你是13皇后问题，limit 最右13个1，其他都是0
            int limit = n == 32 ? -1 : (1 << n) - 1;
            return process2(limit, 0, 0, 0);
        }
    
        // 7皇后问题
        // limit : 0....0 1 1 1 1 1 1 1
        // 之前皇后的列影响：colLim
        // 之前皇后的左下对角线影响：leftDiaLim
        // 之前皇后的右下对角线影响：rightDiaLim
        public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
            if (colLim == limit) {
                return 1;
            }
            // pos中所有是1的位置，是你可以去尝试皇后的位置
            int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
            int mostRightOne = 0;
            int res = 0;
            while (pos != 0) {
                mostRightOne = pos & (~pos + 1);
                pos = pos - mostRightOne;
                res += process2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1,
                        (rightDiaLim | mostRightOne) >>> 1);
            }
            return res;
        }
    
        public static void main(String[] args) {
            int n = 4;
    
            long start = System.currentTimeMillis();
            System.out.println(num2(n));
            long end = System.currentTimeMillis();
            System.out.println("cost time: " + (end - start) + "ms");
    
            start = System.currentTimeMillis();
            System.out.println(num1(n));
            end = System.currentTimeMillis();
            System.out.println("cost time: " + (end - start) + "ms");
    
        }
    }