回溯思想

墨蓝 2023-06-23 02:59 13阅读 0赞

把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先尝试选一条路走，当发现这条路走不通的时候（不符合期望的解），就尝试另外一种走法继续走。  
典型的如：  
8皇后算法，皇后放入当前节点不满足，则尝试别的节点。  
0-1背包，当前物体放入超重，则不放入当前物体。  
背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

练习：8皇后算法书写  
8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。

public class BacktrackingAlgorithm {
    
        public static void main(String[] args) {
            setQueen(0);
    
            int[] items = {4,5,6,7,8,9,10};
            f(0, 0, items, 7, 7);
        }
    
        // 下标表示行，值表示列
        static int[] result = new int[8];
        // 8皇后问题
        public static void setQueen(int row){
            if( row == 8 ){
                printQueens(result);
                return;
            }
            for(int col=0; col<8; col++){
                if(ok(row, col, result)){
                    // 注意：这里虽然执行，但是并没有跳出for循环，所以还会考虑别的可能性
                    result[row] = col;
                    setQueen(row+1);
                }
            }
        }
    
        // 打印出一个二维矩阵
        private static  void printQueens(int[] result) {
            for (int row = 0; row < 8; ++row) {
                for (int column = 0; column < 8; ++column) {
                    if (result[row] == column) System.out.print("Q ");
                    else System.out.print("* ");
                }
                System.out.println();
            }
            System.out.println();
        }
    
        /**
         * desc:判断新的节点是否符合要求，比较难以理解，可以借助xy坐标轴理解
         */
        private static boolean ok(int row, int col, int[] result) {
            int leftdown = col-1, rightdown=col+1;
    
            // 逐行向下遍历是否存在冲突
            for(int i= row-1; i>=0; i--){
                // 比较是否存在列冲突
                if(result[i] == col){
                    return false;
                }
                // 比较左下角,左上角无需比较，因为此时上方肯定还没有皇后
                if(leftdown>=0 && result[i] == leftdown){
                    return false;
                }
                // 为下次比较做准备，列左移
                leftdown--;
    
                // 比较右下角
                if(rightdown<8 && result[i] == rightdown){
                    return false;
                }
                rightdown++;
            }
            return true;
        }
    
    
        // 0-1背包问题：背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。
        // 在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
    
        //存储背包中物品总重量的最大值
        public static int maxW = Integer.MIN_VALUE;
        // i表示考察到哪个物品了；cw表示当前已经装进去的物品的重量和；
        // w背包重量；items表示每个物品的重量；n表示物品个数
        // 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数：
        // f(0, 0, a, 10, 100)
        public static void f(int i, int cw, int[] items, int n, int w ){
            if(i==n || cw==w){
                if(cw > maxW){
                    maxW = cw;
                }
                System.out.println(maxW);
                return;
            }
            // 直接跳过第i个
            f(i+1, cw, items, n ,w);
            // 将第i个放入包中
            if(items[i]+cw<=w){
                f(i+1, cw+items[i], items, n ,w);
            }
        }
    }