回溯法：回溯法通用模版以及模版应用

从一个问题开始

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4]?]

很容易想到 用两个for循环就可以解决。

如果n为100，k为50呢，那就50层for循环，是不是开始窒息。

此时就会发现虽然想暴力搜索，但是用for循环嵌套连暴力都写不出来！

回溯法的本质

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下(但最坏时间复杂度一般来说还是)，还没有更高效的解法。

搜索空间： 子集树

比如简单背包问题的解空间，本质就是一个满二叉树，只不过会通过剪枝避免暴力得出所有可能的解。

这里介绍的模版不会在求解时进行剪枝，因为本人认为这会让一个模版变得较为复杂，可能达到真正意义上的“通用性”，而是在获取到所有可能的解之后再按题目的要求进行筛选。

回溯法:0-1背包问题-CSDN博客

其中两个可行解为：

一个回溯法模版回顾

参考文章：代码随想录

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

?这个模版使用最大的难点就是如何写出终止条件，在递归过程中来存放结果往往会使得这个模版用起来较为困难。所以接下来介绍的模版是直接拿到所有的解之后再按条件进行筛选

推荐回溯法的模版

本质就是拿到一个高为N的树所有的叶子结点

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class KnapsackProblem1 {
    static List<List<Integer>> result = new ArrayList<>();
    //path记录所有的可能,最后结果总共个数必定为2^N
    static LinkedList<Integer> path = new LinkedList<>();
    //N代表着问题规模的大小,即2^N,最终的叶子结点个数就是2^N
    static int N = 4;

    public static void main(String[] args) {
        backtracking();
    }

    public static void backtracking() {
        if (path.size() == N) {
            //找到了一个叶子结点，就保存下来
            //就算这个叶子结点是不满足题目的要求也保存下来
            result.add(new ArrayList<>(path));
            return;
        }
        //往1走代表选择这个元素
        path.add(1);
        backtracking();
        path.removeLast();
        //往0走代表不选择这个元素
        path.add(0);
        backtracking();
        path.removeLast();
    }
}

模版应用

组合问题

回到文章开头的问题

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

添加的solveCombinationProblem仅仅是用来筛选满足条件的解

package DaiMaSuiXiangLu;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class KnapsackProblem1 {
    static List<List<Integer>> result = new ArrayList<>();
    //path记录所有的可能,最后结果总共个数必定为2^N
    static LinkedList<Integer> path = new LinkedList<>();
    //N代表着问题规模的大小,即2^N,最终的叶子结点个数就是2^N
    static int N = 4;

    public static void main(String[] args) {
        //组合问题
        int K = 2;
        solveCombinationProblem(K);


    }

    public static void backtracking() {
        if (path.size() == N) {
            //找到了一个叶子结点，就保存下来
            //就算这个叶子结点是不满足题目的要求也保存下来
            result.add(new ArrayList<>(path));
            return;
        }
        path.add(1);
        backtracking();
        path.removeLast();
        path.add(0);
        backtracking();
        path.removeLast();
    }
    public static void solveCombinationProblem(int k) {
        int time = 0;
        for (int i = 0; i < result.size(); i++) {
            //用来记录该叶子结点中1的个数
            time = 0;
            List<Integer> answer = result.get(i);
            for (int j = 0; j < answer.size(); j++) {
                if (answer.get(j) == 1) {
                    time++;
                }
            }
            if (time == k) {
                for (int j = 0; j < answer.size(); j++) {
                    if (answer.get(j) == 1) System.out.print((j + 1) + " ");
                }
                System.out.println();
            }

        }
    }
}

0-1背包问题?

用之前回溯法的模版会发现终止条件不好写出来

回溯法:0-1背包问题-CSDN博客

但用该文章推荐的模版很好地解决这个问题

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class KnapsackProblem1 {
    static List<List<Integer>> result = new ArrayList<>();
    //path记录所有的可能,最后结果总共个数必定为2^N
    static LinkedList<Integer> path = new LinkedList<>();
    //N代表着问题规模的大小,即2^N,最终的叶子结点个数就是2^N
    static int N = 4;

    public static void main(String[] args) {
        backtracking();
        //背包问题
        int[] items_weight={8,6,4,3};
        int[] items_value={12,11,9,8};
        int C=13;
        solveKnapsackProblem(items_weight,items_value,C);

    }

    public static void backtracking() {
        if (path.size() == N) {
            //找到了一个叶子结点，就保存下来
            //就算这个叶子结点是不满足题目的要求也保存下来
            result.add(new ArrayList<>(path));
            return;
        }
        path.add(1);
        backtracking();
        path.removeLast();
        path.add(0);
        backtracking();
        path.removeLast();
    }

    public static void solveKnapsackProblem(int[] items_weight, int[] items_value, int C) {
        //值得注意的是items_weight和items_value的长度都为N
        int sum_weight = 0;
        int sum_value = 0;
        //记录现在能达到的最大价值
        int max_value = -1;
        for (int i = 0; i < result.size(); i++) {
            sum_weight = 0;
            sum_value = 0;
            List<Integer> answer = result.get(i);
            for (int j = 0; j < answer.size(); j++) {
                if (answer.get(j) == 1) {
                    sum_value += items_value[j];
                    sum_weight += items_weight[j];
                }
            }
            //不高于背包容量且比之前找到的最大价值还大
            if (sum_weight <= C && sum_value > max_value) {
                max_value = sum_value;
            }
        }
        System.out.println(max_value);
    }
}