13回溯
一、回溯1
例题1–递归实现排列型枚举-蓝桥19684
1.递归可以解决不定次数的循环问题
2.使用数组来标记数字是否被选过
import java.util.Scanner;public class Main {static int n;static boolean[] st = new boolean[10]; //判断数字是否被选过static int[] path = new int[10]; //存储排列组合//递归程序public static void dfs(int u){if(u > n){//递归结束的条件，递归结束就输出结果。（但这里其实是针对每一次的排序而言）for (int i = 1; i <= n; i++) {System.out.print(path[i] + " ");}System.out.println();return;}//递归--循环排列组合for (int i = 1; i <= n ; i++) {if(st[i]) continue;st[i] = true;//选中path[u] = i; //记录dfs(u + 1); //下一个数的循环st[i] = false; //解除}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();dfs(1);
/* for (int i = 1; i <= n ; i++) {st[i] = true;for (int j = 1; j <= n ; j++) {
// if(j == i) continue;if(st[j]) continue;st[j] = true;for (int k = 1; k <= n ; k++) {
// if (k == i || k ==j) continue;if(st[k]) continue;System.out.println(i+ "," + j + "," + k);}st[j] = false;}st[i] = false;}*/}
}
*特别注意！！！
结果对但是没有通过用例，原因是输出的格式问题！各个数之间要用空格隔开！这点特别需要注意。
例题2–串变换蓝桥4360
对k个操作进行全排列。以及k--的排列，直到可以变为T串，或循环到最后都变不了
例题3–带分数蓝桥208
回溯+枚举
思路，1-9出现且只出现1次，进行9的全排列，把9个数的所有组合排列出来，再把加号和除号放进去，看看哪些符合条件
import java.util.*;public class Main {static int N;static int count = 0;//static List<String> permutations = new ArrayList<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);N = sc.nextInt();sc.close();// 生成1~9的所有排列permute("123456789", 0, 8);System.out.println(count);}// 生成全排列public static void permute(String str, int l, int r) {if (l == r) {//permutations.add(str);check(str);} else {for (int i = l; i <= r; i++) {str = swap(str, l, i);permute(str, l + 1, r);str = swap(str, l, i); // 回溯}}}// 检查所有的加号和除号位置public static void check(String str) {for (int i = 1; i <= 7; i++) { // 加号位置，要大于0for (int j = i + 1; j <= 8; j++) { // 除号位置，在加号的右边int A = Integer.parseInt(str.substring(0, i));int B = Integer.parseInt(str.substring(i, j));int C = Integer.parseInt(str.substring(j));// 避免除0错误if (C == 0) continue;// 判断是否符合 A + B / C = Nif (A + (double) B / C == N) {count++;}}}}// 字符串交换工具方法public static String swap(String str, int i, int j) {char[] charArray = str.toCharArray();char temp = charArray[i];charArray[i] = charArray[j];charArray[j] = temp;return new String(charArray);}
}1234
1243
1324
1342
1432
1423
2134
2143
2314
2341
2431
2413
3214
3241
3124
3142
3412
3421
4231
4213
4321
4312
4132
4123
理解回溯中的关键操作
str = swap(str, l, i);
- 做选择：交换当前元素和
i位置的元素，相当于尝试将i放在当前的位置。
permute(str, l + 1, r);
- 递归调用：继续处理后面的数字，进入下一层。
str = swap(str, l, i);
- 撤销选择：把字符串恢复到原来的状态，确保不影响下一次的尝试。
- 这是 回溯的精髓：探索完一条路径后，将状态恢复，以便继续探索其他路径。
建议：用树状图画出回溯的执行过程，一步步理解状态的变化。
几道回溯小题
二、回溯2
例题–N皇后问题蓝桥1508
题目要求也不允许处在与棋盘边框成 45 角的斜线上。（注意与棋盘边框）
主对角线
副对角线
暴力做法
假设n=4，进行4次循环的嵌套，每一次代表的是每一行棋子的位置。
public class Main {static int N = 30;//行row，列col，主对角线zhu，副对角线fustatic boolean[] row = new boolean[N];static boolean[] col = new boolean[N];static boolean[] zhu = new boolean[N];static boolean[] fu = new boolean[N];public static void main(String[] args){int ans = 0;//记录//一个for表示一行for (int i = 1; i <= N; i++) {//尝试第1个棋子int x1 = 1,y1 = i;//行//列//被选中了就为truerow[x1] = true;col[y1] = true;zhu[N - y1 + x1] = true;fu[x1 + y1] = true;for (int j = 1; j <= N; j++) {//尝试第2个棋子int x2 = 2,y2 = j;//行//列//不符合规则的就跳过if(row[x2] || col[y2] || zhu[N - y2 + x2] || fu[x2 + y2]) continue;//被选中了就为truerow[x2] = true;col[y2] = true;zhu[N - y2 + x2] = true;fu[x2 + y2] = true;for (int k = 1; k <= N; k++) {//尝试第3个棋子//同样for (int l = 1; l <= N; l++) {//尝试第4个棋子//同样，顺便ans加加}}//结束要释放//回溯row[x2] = false;col[y2] = false;zhu[N - y2 + x2] = false;fu[x2 + y2] = false;}//结束要释放//回溯row[x1] = false;col[y1] = false;zhu[N - y1 + x1] = false;fu[x1 + y1] = false;}}
}
其实上面的row数组是没必要的，因为循环的就是行数，按行数来的。
dfs递归做法
import java.util.Scanner;//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {static int ans;static int n;static int N = 30;//行row，列col，主对角线zhu，副对角线fu//static boolean[] row = new boolean[N];static boolean[] col = new boolean[N];static boolean[] zhu = new boolean[N];static boolean[] fu = new boolean[N];//递归函数public static void dfs(int u){if(u > n){//循环到最后ans++;return;}for (int i = 1; i <= n; i++) {//这表示每一行循环每一列,因此i表示的是列数，u表示的是行数//首先判断是否被占用if(col[i] || zhu[n - i + u] || fu[u + i]) continue;//选中一个数col[i] = true;zhu[n - i + u] = true;fu[u + i] = true;//递归下一行dfs(u + 1);//回溯col[i] = false;zhu[n - i + u] = false;fu[u + i] = false;}}//主逻辑函数public static void solve(){//输入NScanner sc = new Scanner(System.in);n = sc.nextInt();//调用dfs(1);System.out.println(ans);}public static void main(String[] args) {solve();}
}
学到的知识点：
1.难点：本题要求不能在同一行，同一列和与棋盘边框成45度角。
45度角这个需要找规律。
把这些情况都转换为设为一个布尔数组，来判断是否被放置。true--被放置，false--没有。
2.学习到的递归知识：
首先，设n为4，进行一个暴力的做法。
就是遍历每一行，对于每一行，判断某个位置是否符合条件（1中的条件）。
符合条件后，设定其被放置，进行下一层遍历。否则continue。
对于一次找到合法的放置位置后，需要将位置进行释放--这就是回溯。因此，将暴力的做法转为递归，就容易了。
找到一个合法的放置位置（u>x后），ans++；
递归函数中，为每一行的遍历。
一行遍历完后进行下一行的递归（dfs(u + 1)）;
下面几行回溯。
写完代码看完视频又忘记思路，不好说。只可意会。
三、回溯3-子集枚举（递归实现指数型枚举）
一旦涉及选与不选，删和不删，留和不留-->两种状态-->就要想到子集枚举
例题1–递归实现指数型枚举19685
其实看不懂这个题目，好奇怪的题目。根据老师的解析来写。
大致理解为从1-n中，输出所有的组合数就对了。
我知道了，就是要按照题目的要求来，要先判断0不选，再判断1选。具体看代码更了解。
暴力做法
假设n=3.
public class Main {static int[] st = new int[10];//主逻辑函数public static void solve(){int n = 3;for (int i = 0; i <=1; i++) {//表示选或不选st[1] = i;for (int j = 0; j <= 1; j++) {//表示选或不选st[2] = j;for (int k = 0; k <= 1; k++) {//表示选或不选st[3] = k;for (int l = 1; l <= 3; l++) {//选中的输出if(st[l] == 1) System.out.print(l);}System.out.println();}}}}public static void main(String[] args) {solve();}
}
使用回溯dfs来实现
import java.util.Scanner;//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {static int n;static int[] st = new int[20];//递归函数public static void dfs(int u){if(u > n){//一次结束，输出结果for (int l = 1; l <= n; l++) {//选中的输出if(st[l] == 1) System.out.print(l + " ");}System.out.println();return;//这里要返回，因为？}for (int i = 0; i <= 1; i++) {st[u] = i;dfs(u + 1);//下一个数选或不选}}//主逻辑函数public static void solve(){Scanner sc = new Scanner(System.in);n = sc.nextInt();dfs(1);
// for (int i = 0; i <=1; i++) {//表示选或不选
// st[1] = i;
// for (int j = 0; j <= 1; j++) {//表示选或不选
// st[2] = j;
// for (int k = 0; k <= 1; k++) {//表示选或不选
// st[3] = k;
// for (int l = 1; l <= 3; l++) {
// //选中的输出
// if(st[l] == 1) System.out.print(l);
// }
// System.out.println();
// }
// }
// }}public static void main(String[] args) {solve();}
}
特别注意输出的格式问题，空格或者逗号特别注意，总因为这个没通过！！！
例题2–19880
例题3–蛋糕的美味值8664
package huisu;import java.util.Scanner;public class TasteCake {static int[] cake = new int[30];static int[] st = new int[30];static int n,k;static int max;//获得最大的总和public static void getMax(){int sum = 0;for (int i = 1; i <= n; i++) {if(st[i] == 1){//被选中并且美味值小于ksum += cake[i];}}//结束后返回目前最大值if(sum < k){max = Math.max(sum,max);}}//递归public static void dfs(int u){//u表示第几个蛋糕if(u > n){//表示n个蛋糕选与不选完了getMax();return;}for (int i = 0; i <= 1; i++) {//选与不选st[u] = i;dfs(u + 1);//下一个蛋糕}}//主逻辑函数public static void solve(){Scanner sc = new Scanner(System.in);//输入n，kn = sc.nextInt();k = sc.nextInt();//输入蛋糕的美味值for (int i = 1; i <= n; i++) {cake[i] = sc.nextInt();}//递归dfs(1);//输出结果System.out.println(max);}public static void main(String[] args) {solve();}
}注意：
一定要看清题目啊，看题目和观察样例。
这里是要选出的蛋糕的总值小于k，而不是选出的每一个小于k的。
我第一次写理解为后面那一种，就错了。
其实看样例也能看出来。
题目真难理解。。。
例题4–luoguP1036
思想
老师说只需要思考最后两层的递归，其他层的递归其实就和最后两层一样
对于选与不选的递归问题，事件复杂度都是2^n，对于n<=25的都可以运行
