本文共 12535 字，大约阅读时间需要 41 分钟。
DFS 深搜专题 入门典例 -- 凌宸1642
深度优先搜索 是一种 枚举所有完整路径以遍历所有情况的搜索方法 ，使用 递归 可以很好的实现 深度优先搜索。
1 最大价值
题目描述
有 n 件物品，每件物品的重量为 w[i] , 价值为 c[i] 。现在需要选出若干件物品放入一个容器为 V 的背包中，使得在选入背包的物品重量和不超过容量 V 的前提下 ，让背包中的物品的价值之和最大，求最大价值。(1 ≤ n≤ 20 )
输入描述：
第一行输入物品总数 n 和 背包容量 v 。
第二行输入 n 个整数， 分别表示 n 件物品各自的重量。
第三行输入 n 个整数， 分别表示 n 件物品各自的价值。
输出描述：
对于每个测试用例，在一行中输出最大价值。
样例输入：
5 83 5 1 2 24 5 2 1 3样例输出：
10
#include<bits/stdc++.h>using namespace std ;#define MAX 30int n , v , maxValue = 0 ; // 物品件数 n，背包容量 v,最大价值 maxValue int w[MAX] , c[MAX] ; // w[i]为每件物品的重量， c[i]每件物品的价值// dfs ，index 表示当前处理物品的编号 ， sumW sumC 分别为当前 总重量 和 总价值void dfs(int index , int sumW , int sumC){ if(index == n) { // 已经完成对 n 件物品的处理 if(sumW <= v && sumC > maxValue ) maxValue = sumC ; // 如果此时最大价值符合题意，则更新 return ; } // 岔道口 dfs(index + 1 , sumW , sumC) ; // 不选择第 index 件物品 dfs(index + 1 , sumW + w[index] , sumC + c[index]) ; // 选择了第 index 件物品 } int main(){ cin >> n >> v ; // 输入 物品数 n 和 背包容量 v for(int i = 0 ; i < n ; i ++) cin >> w[i] ; // 输入 n 件物品的 重量 for(int i = 0 ; i < n ; i ++) cin >> c[i] ; // 输入 n 件物品的 价值 dfs(0 , 0 , 0) ; // 调用 dfs 进行深搜 cout << maxValue << endl ; // 深搜结束后， maxValue 中存有最大价值，直接输出 return 0;}// 对此 dfs 进行剪枝后 ，剪枝是在保证算法正确的情况下，通过题目条件限制来减少 DFS 计算量的方法void dfs(int index , int sumW , int sumC){ if(index == n) return ; //完成对 n 件物品的选择 dfs(index + 1 , sumW , sumC) ; // 未选择第 index 件物品 if(sumW + w[index] <= v ) { // 只有当选择第 index 件物品之后，容量不会超过 v ，才进行选择 if(sumC + c[index] > maxValue) maxValue = sumC + c[index] ; // 更新最大价值 maxValue dfs(index + 1 , sumW + w[index] , sumC + c[index]) ; // 选择第 index 件物品 }}2 最优方案
题目描述：
给定一个序列，枚举这个序列的所有子序列(可以不连续)。例如对序列{1,2,3}来说，他的所有子序列为{1}，{2}，{3}，{1,2}，{1,3}，{1,2,3}。枚举所有子序列的目的很明显——可以从中选择一个“最优”子序列，使它的某个特征是所有子序列中最优的；如果有需要，还可以将这个最优子序列保存下来。显然，这个问题也可以等价于 枚举从 N 个整数中选择 K 个数的所有方案。
给定
N个整数（可能有负数），从中选择K个数，使得这K个数的和恰好等于给定的一个整数X； 如果有多种方案，则选择他们当中平方和最大的一个。数据保证这样的方案唯一。例如，从 4 个整数{2,3,3,4}中选择两个数，使他们的和为 6 。显然有两种方案{2,4} 和{3,3} ，其中平方和最大的方案为{2,4}。输入描述：
第一行输入
3个正整数 ，依次输入序列的长度N，从中选择数的数量K，和恰好等于的和X。 第二行输入
N个整数（可能有负数），表示序列中的数。输出描述：
输出分两行，第一行输出
K个数 , 表示最优序列中的元素。元素之间用空格分隔，且行末没有于的空格 第二行输出 最优方案的平方和。
样例输入：
4 2 62 3 3 4样例输出：
2 420
#include<bits/stdc++.h>using namespace std ;#define MAX 100010int n , k , x , maxSumSqu = - 1 , a[MAX] ;//分别表示，序列长度，选择数量，恰好的和，最大平方和，序列vector<int> temp , ans ; // temp 存放临时方案，ans 存放平方和最大的方案 // dfs参数列表分别表示 处理第 index 个数，现在已选 nowK 个数，当前已选数字的和 sum 及其平方和 sumSquvoid dfs(int index , int nowK , int sum , int sumSqu){ // 找到第 k 个数的和为 x if(nowK == k && sum == x){ if(sumSqu > maxSumSqu){ // 如果比当前的更优 maxSumSqu = sumSqu ; // 更新最大平方和 ans = temp ; // 更新最优方案 } return ; } // 已经处理完 n 个数，或者超过 k 个数，或者和超过 x，返回 if(index == n || nowK > k || sum > x) return ; // 选第 index 个数 temp.push_back(a[index]) ;// 将第 index 个数 入栈，然候搜索下一个数，注意参数各个值的变化 dfs(index + 1 , nowK + 1 , sum + a[index] , sumSqu + a[index] * a[index]) ; // 不选第 index 个数 temp.pop_back() ; // 先将第 index 个数 出栈( 还原现场 ) dfs(index + 1 , nowK , sum , sumSqu) ; // 继续搜索下一个数}int main(){ //cin >> n >> k >> x ; scanf("%d%d%d" , &n , &k , &x) ;// 依次输入序列的长度 n ， 选择数的数量 k ，恰好的和 x for(int i = 0 ; i < n ; i ++) scanf("%d" , &a[i]) ; // 输入序列 dfs(0 , 0 , 0 , 0) ; // 调用 dfs for(int i = 0 ; i < ans.size() ; i ++){ // dfs 后 ， ans中存储的是最优子序列，遍历输出 //cout<< ans[i]<<" " ; printf("%d%c" , ans[i] , (i == ans.size() - 1)?'\n':' ') ; } printf("%d\n" , maxSumSqu) ; // 输出最优子序列的 平方和 // cout<<endl<<maxSumSqu<<endl ; return 0 ;}3 全排列
题目描述：
排列与组合是常用的数学方法。先给一个正整数 ( 1 < = n < = 10 ) 。例如n＝3，所有组合,并且按字典序输出：
1 2 31 3 22 1 32 3 13 1 23 2 1输入描述：
在一行中输入正整数 n ( 1 < = n < = 10 ) 。
输出描述：
按字典序输出 n 的全排列。每行输出一个排列，数字间用空格分隔，且行末没有多与的空格
样例输入：
3样例输出：
1 2 31 3 22 1 32 3 13 1 23 2 1
#include<bits/stdc++.h>using namespace std ;#define MAX 20 bool flag[20] = { false } ; // 是否被访问，初值为 falseint num[20] ; // 存储排列int n ; // dfs 参数 index 表述处理排列的第 index 个数void dfs(int index){ if(index == n + 1){ // 如果 index 等于 n + 1 ，表明已经完成了一次排列 ，则当前排列 // printf("%d" , num[1]) ; 输出第一个元素 // for(int i = 2 ; i <= n ; i ++)printf(" %d" ,num[i]); 输出空格和后面 n - 1 个元素 // printf("\n") ; 当前排列全部输出，换行 // 上述四条语句，等价于如下语句 for(int i = 1 ; i <= n ; i ++) printf("%d%c" , num[i] , (i == n)?'\n':' '); return ; } for(int i = 1 ; i <= n ; i ++){ // n 的全排列，就是将 1 - n 都访问一遍 ， 并存在对应位置 if(flag[i] == false){ // 如果 i 还未访问 num[index] = i ; // 将 i 的值存入 num 数组第 index 位置 flag[i] = true ; // 将 i 的访问标志置为 true dfs(index + 1) ; // 进行下一个位置的 dfs 搜索 flag[i] = false ; // 还原现场 } }}int main(){ scanf("%d" , &n) ; // 输入正整数 n dfs(1) ; // 调用 dfs return 0;}4 组合的输出
题目描述：
排列与组合是常用的数学方法，其中组合就是从
n个元素中抽出r个元素(不分顺序且r ≤ n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。 例如n ＝ 5 ，r ＝ 3，所有组合为：1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5输入描述：
在一行中输入两个自然数
n，r( 1 < n < 21，1 ≤ r ≤ n )。输出描述：
输出所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，所有的组合也按字典顺序。每行中的元素之间用空格分隔，并且行末没有多余的空格。
样例输入：
5 3样例输出：
1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5
#include<bits/stdc++.h>using namespace std ;int n , r ;vector<int> temp ; // temp 存储当前已选的数// index 为当前处理的数的下标， nowR是已经有多少个数 void dfs(int index , int nowR){ if(nowR == r){ // 如果已选 k 个数，那么输出当前选择的 k 个数// printf("%d" ,temp[0]);// for(int i = 1 ; i < r ; i ++) printf(" %d" , temp[i]);// printf("\n"); for(int i = 0 ; i < r ; i ++) printf("%d%c" , temp[i] , (i == r - 1)?'\n':' '); return ; } // 如果已经处理完 n 个数 或者选择数的数量大于 k if(index == n + 1 || nowR > r) return ; // 选第 index 个数 temp.push_back(index) ; // 将 index 入栈 dfs(index + 1 , nowR + 1) ; // 继续 dfs 深搜 注意参数的变化 // 不选第 index 个数 temp.pop_back() ; // 先将 index 出栈 dfs(index + 1 , nowR) ; // 继续 dfs 深搜 注意参数的变化}int main(){ scanf("%d%d" , &n, &r) ; dfs(1 , 0) ; // 调用 dfs 下标解释为 从 1 开始搜索，当前选择数的数量为 0 return 0 ;}5 组合+判断素数
题目描述：
已知
n个整数b1,b2,…,bn。以及一个整数k（k＜n）。 从n个整数中任选k个整数相加，可分别得到一系列的和。例如当 n = 4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：3＋7＋19＝29。
输入描述：
第一行两个整数：`n` , `k` `(1 ≤ n ≤ 20，k < n)` 第二行
n个整数：x1,x2，… , xn (1 ≤ xi ≤ 5000000)输出描述：
一个整数（满足条件的方案数）。
样例输入：
4 33 7 12 19样例输出：
1
#include<bits/stdc++.h>using namespace std ;int num[22] ; // 存储选择的数int n , k , ans = 0 ; // ans 用来存储满足要求的方案数的数量// 判断一个数是否为素数的算法 就不必再赘述了bool isPrime(int x){ if(n <= 1 || n == 2) return false ; for(int i = 2 ; i <= sqrt(x) ; i ++){ if(x % i == 0) return false ; } return true ;}// dfs 参数说明：分别表示 处理第 index 个数，当前已选 nowK 个数 ，当前已选数字的和void dfs(int index , int nowK ,int sum){ if(nowK == k){ // 如果已选 k 个数 if(isPrime(sum)) // 判断当前 k 个数的和 是否为素数， ans ++ ; // 如果是，则方案数 自增 1 return ; } // 已经处理了 n 个数 ， 或者 所选数的数量大于 k ，则返回 if(index == n + 1 || nowK > k) return ; // 选第 index 个数 ；注意 对应参数变化 dfs(index + 1 , nowK + 1 , sum + num[index]) ; // 不选第 index 个数 ； dfs(index + 1 , nowK , sum) ; } int main(){ scanf("%d%d" , &n ,&k) ; // 输入 n 和 k for(int i = 1 ; i <= n ; i ++) scanf("%d" ,&num[i]) ; // 输入 n 个整数 dfs(1 , 0 , 0) ; // dfs 调用， 处理第 1 个数 当前所选数的数量为 0 当前所选数字的和为 0 printf("%d\n" , ans) ; // 输出满足要去的结果数 return 0;}6 N 皇后问题
题目描述：
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将 8 个皇后放在棋盘上（有 8 * 8 个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
输入描述：
一个整数
n（ 1 ≤ n ≤ 10 )。输出描述：
每行输出对应一种方案，按字典序输出所有方案。每种方案顺序输出皇后所在的列号，相邻两数之间用空格隔开，行末没有多与的空格。如果一组可行方案都没有，输出
no solute!。样例输入：
4样例输出：
2 4 1 33 1 4 2
#include<bits/stdc++.h>using namespace std ;int n , temp[12] = { 0 } ,cnt = 0 ; // temp 用来存储当前摆放皇后的列标 ， cnt 用来记录解的个数bool p[12] = { false } ; // 列表的访问数组 ， 初值为 false 代表都未被访问// dfs 参数 index 表示当前处理 第 index 列void dfs(int index){ if(index == n + 1){ // 已经处理完 n 列 ， 输出当前 temp 中存储的摆放顺序 cnt ++ ; //printf("%d" ,temp[1]); //for(int i = 2 ; i <= n ; i ++) printf(" %d" , temp[i]); //printf("\n"); for(int i = 1 ; i <= n ; i ++) printf("%d%c" , temp[i] , (i == n)?'\n':' ') ; return ; } // 对于 摆放皇后的位置，遍历第 i 到 n 列 for(int i = 1 ; i <= n ; i ++){ if(p[i] == false){ // 如果当前列没有皇后 bool flag = true ; // 定义标志位，看是否对角线上有皇后 for(int pre = 1 ; pre < index ; pre ++){ // 遍历已经摆放好的皇后 // 回溯 if(abs(index - pre) == abs(i - temp[pre])){ // 如果在某一对角线有冲突 flag = false ; // 标志位置为 false ，并跳出循环 break; } } if(flag){ // 如果对角线没有冲突 temp[index] = i ; // 将当前列标复制给 temp 的第 index ，即在当前列放一个皇后 p[i] = true ; // 并置当前位置的访问位 为true 表示已经访问过 dfs(index + 1) ; // 继续 dfs ，摆放下一个位置的皇后 p[i] = false ; // 还原现场 } } }}int main(){ scanf("%d" , &n) ; // 输入 n 皇后 的规模 n dfs(1) ; // 从 第 1 列开始 dfs if(cnt == 0) printf("no solute!\n") ; // 如果解的数目为 0 即无解，按题目要求输出 no solute! return 0;}7 出栈序列统计
题目描述：
栈是常用的一种数据结构，有
n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，… ，n，经过一系列操作可能得到的输出序列总数。输入描述：
一个整数
n (1 ≤ n ≤ 15).输出描述：
一个整数，即可能输出序列的总数目。
样例输入：
3样例输出：
5
#include<bits/stdc++.h>using namespace std ;int n , cnt = 0 ;// dfs 参数解析，in 代表栈中有多少个元素 ， out 代表还有多少元素需要入栈void dfs(int in , int out){ if(out == 0){ // 如果以及没有需要进栈的元素，那么出栈顺序总数目 + 1 cnt ++ ; return ; } if(in == 0) dfs(in + 1,out - 1) ; // 如果栈中没有元素，则只能进行入栈操作 else if (out != 0){ // 如果栈中有元素，也存在待入栈的元素 dfs(in + 1 , out - 1 ) ; // 进行入栈操作 dfs(in - 1 , out) ; // 进行出栈操作 }}int main(){ scanf("%d" , &n) ; dfs(0 , n) ; // 调用 dfs 初始栈内元素个数为 0 ，需要入栈元素为 n printf("%d\n" , cnt) ; // 输出解的个数 return 0 ;}8 走迷宫
题目描述：
有一个n * m格的迷宫(表示有 n 行、m 列)，其中有可走的也有不可走的，如果用 1 表示可以走，0 表示不可以走，文件读入这 n * m个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。 请统一用 左上右下的顺序拓展，也就是 (0,-1),(-1,0),(0,1),(1,0)
输入描述：
第一行是两个数
n，m ( 1 < n ， m < 15 )，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。输出描述：
所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用
->表示方向。 如果没有一条可行的路则输出-1。样例输入：
5 61 0 0 1 0 11 1 1 1 1 10 0 1 1 1 01 1 1 1 1 01 1 1 0 1 11 15 6样例输出：
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)提示信息：
用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪些点走过了。每个点用两个数字来描述，一个表示行号，另一个表示列号。对于某一个点(x，y)，四个可能走的方向的点描述如下表：
2
1 x,y 3
4
对应的位置为：(x, y-1)，(x-1, y)，(x, y+1)，(x+1, y)。所以每个点都要试探四个方向，如果没有走过(数组b相应的点的值为0)且可以走(数组a相应点的值为1)同时不越界，就走过去，再看有没有到达终点，到了终点则输出所走的路，否则继续走下去。
这个查找过程用search来描述如下：
procedure search(x, y, b, p)；{x，y表示某一个点，b是已经过的点的情况，p是已走过的路}
begin
for i:＝1 to 4 do{分别对4个点进行试探}
begin
先记住当前点的位置，已走过的情况和走过的路；
如果第i个点(xi，yi)可以走，则走过去；
如果已达终点，则输出所走的路径并置有路可走的信息，
否则继续从新的点往下查找search(xi，yi，b1，p1)；
end；
end；
有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层的结点，看起来如同树枝一样，对于其中的“枯枝”——明显无用的节点可以先行“剪掉”，从而提高搜索速度。
#include<bits/stdc++.h>using namespace std ;#define MAX 20// 下列变量代表迷宫的维数， 解的数量，起始坐标和出口坐标 int n , m , num = 0 , startX , startY , endX , endY ;int labyrinth[MAX][MAX] = { 0 } ; // 存储迷宫的二维数组 int dx[4] = {0 , -1 , 0 , 1 } ; int dy[4] = {-1 , 0 , 1 , 0 } ; // 表示上下左右的扩展// 代表所有是解的路径上的点的数量(除终点) vector<pair<int , int > > road ; //保存路线的向量，每个元素的有x、y坐标 // x ,y 代表当前处理的坐标点，void dfs(int x , int y ){ road.push_back(make_pair(x , y )) ; // 当前坐标的赋值 if(x == endX && y == endY){ // 如果已经走到出口位置，输出这条路径 for(int i = 0 ; i < road.size() ; i ++){ printf("(%d,%d)" , road[i].first , road[i].second) ; if(i != road.size() - 1) printf("->") ; } printf("\n") ; num ++ ;// 解的数量加 1 return ; } // 遍历当前坐标的左，上，右，下位置的点 for(int j = 0 ; j < 4 ; j ++){ // 如果进行 左，上，右，下 扩展后，得到的点依旧未被访问且 在迷宫的范围内 if(labyrinth[x + dx[j]][y + dy[j]] == 1 && 1 <= x + dx[j] <= m && 1 <= y + dy[j] <= n){ labyrinth[x][y] = 0 ; //当前点以遍历，不可访问 dfs(x + dx[j] , y + dy[j]) ; // 选择某个位置(左，上，右，下)，继续遍历搜索 road.pop_back() ; // 当前元素出栈 labyrinth[x][y] = 1 ; // 还原现场 } } }int main(){ scanf("%d%d" , &m , &n) ;// 输入迷宫的行与列的值 for(int i = 1 ; i <= m ; i ++){ for(int j = 1 ; j <= n ; j ++){ scanf("%d" , &labyrinth[i][j]) ; // 输入迷宫 } } scanf("%d%d" , &startX , &startY) ; // 输入起始点坐标 scanf("%d%d" , &endX , &endY) ;// 输入终点坐标 dfs(startX , startY) ; // 从输入的起点开始 dfs if(num == 0) printf("-1\n") ; // 如果找不到路径，则输出 -1 return 0 ;}