实例一 0/1背包问题：
有n件物品，每件物品的重量为w[i]，价值为c[i]。现在需要选出若干件物品放入一个容量为V的背包中，使得在选入背包的物品重量和不超过容量V的前提下，让背包中的物品价值之和最大，求最大价值。（1<=n<=20）
/**
* Copyright(c)
* All rights reserved.
* Author : Mered1th
* Date : 2019-02-20-13.12.15
* Description : Bag
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_set>
#include<map>
#include<vector>
#include<set>
using namespace std; const int maxn=30;
int n,V,maxValue=0;//物品件数，背包容量，最大价值
int w[maxn],c[maxn]; //每件物品的重量，每件物品的价值
void DFS(int index,int sumW,int sumC){
if(index==n){
if(sumW<=V&&sumC>maxValue){
maxValue=sumC;
}
return;
}
DFS(index+1,sumW,sumC); //不选
DFS(index+1,sumW+w[index],sumC+c[index]); //选
} int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
scanf("%d%d",&n,&V);
for(int i=0;i<n;i++){
scanf("%d",&w[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&c[i]);
}
DFS(0,0,0);
printf("%d\n",maxValue);
return 0;
}
输入：
5 8
3 5 1 2 2
4 5 2 1 3
输出：
10
上述方法在加入全部n件物品之后才更新最大价值，实际上可对sumW提前判断，若sumW+w[index]<=V，则再进入选择
void DFS2(int index,int sumW,int sumC){
if(index==n){
return;
}
DFS2(index+1,sumW,sumC);
if(sumW+w[index]<=V){ //放的进去则选index件物品
if(sumC+c[index]>maxValue){
maxValue=sumC+c[index];
}
DFS2(index+1,sumW+w[index],sumC+c[index]);
}
}
回溯法：
bool in[maxn]={0};
void DFS3(int index,int sumW,int sumC){
if(index==n||sumW>=V){
if(sumC>maxValue){
maxValue=sumC;
}
return;
}
int i=index;
for(;i<n;i++){
if(w[i]+sumW<=V && in[i]==false){ //如果能放进去，且该物品不在背包里面
sumW+=w[i];
sumC+=c[i];
in[i]=true;
DFS3(index+1,sumW,sumC);
sumW-=w[i]; //回溯
sumC-=c[i];
in[i]=false;
}
}
}
回溯法输出最优方案（假设最优方案只有一种。。。如果有多种暂时还没想到怎么写。。。）
vector<int> ans;
map<int,vector<int> > temp;
void DFS4(int index,int sumW,int sumC){
if(index==n||sumW>=V){
if(sumC>maxValue){
maxValue=sumC;
temp[maxValue]=ans;
}
return;
}
int i=index;
for(;i<n;i++){
if(w[i]+sumW<=V&&in[i]==false){
sumW+=w[i];
sumC+=c[i];
in[i]=true;
ans.push_back(i);
DFS4(index+1,sumW,sumC);
ans.pop_back();
sumW-=w[i];
sumC-=c[i];
in[i]=false;
}
}
} int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
scanf("%d%d",&n,&V);
for(int i=0;i<n;i++){
scanf("%d",&w[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&c[i]);
}
DFS4(0,0,0);
printf("%d\n",maxValue);
for(int i=0;i<temp[maxValue].size();i++){
cout<<temp[maxValue][i]<<" ";
}
return 0;
}
实例二 序列的全部子序列：
问题：给定一个序列，枚举这个序列的所有子序列（可以不连续），例如对序列{1,2,3}来说，它的所有子序列为{1}、{2}、{3}、{1,2}，{1,3}、{2,3}、{1,2,3}。
分析：传入参数需要三个，一个是输入序列，一个是输出序列，再加一个变量index用来标记当前位于输入序列的位置。另外还需要用一个容器来存储子序列
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_set>
#include<map>
#include<vector>
#include<set>
using namespace std;
vector<int> ans;
void dfs(string str,int index,string res){
if(index==str.length()){
if(res.size()==0) return; //否则会把“”也输出
int temp=stoi(res);
ans.push_back(temp);
return;
}
dfs(str,index+1,res); //选index
dfs(str,index+1,res+str[index]);//不选index
}
int main(){
string a="123";
dfs(a,0,"");
sort(ans.begin(),ans.end()); //排序
for(auto it=ans.begin();it!=ans.end();it++){
cout<<*it<<endl;
}
return 0;
}
变式：给定N个整数（可能有负数），从中选择K个数，使得这K个数之和恰好等于一个给定的整数X；如果有多种方案，选择他们中元素平方和最大的一个。
const int maxn=110;
int n,k,x,maxsumSqu=-1,A[maxn];
vector<int> temp,ans;
void DFS(int index,int nowK,int sum,int sumSqu){
if(nowK==k && sum==x){
if(sumSqu>maxsumSqu){
maxsumSqu=sumSqu;
ans=temp;
}
return;
}
if(index==n || nowK>k || sum>x){
return;
}
temp.push_back(A[index]);
DFS(index+1,nowK+1,sum+A[index],sumSqu+A[index]*A[index]);
temp.pop_back();
DFS(index+1,nowK,sum,sumSqu);
}
实例三 全排列问题：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_set>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=10;
bool isUsed[maxn]={0};
vector<int> num;
int n;
void dfs(int index){
if(index==n){
for(int i=0;i<num.size();i++){
printf("%d",num[i]);
}
printf("\n");
return;
}
for(int i=1;i<=n;i++){
if(isUsed[i]==true) continue;
num.push_back(i);
isUsed[i]=true;
dfs(index+1);
num.pop_back();
isUsed[i]=false;
}
} int main(){
n=3;
dfs(0);
return 0;
}
实例四 素数环问题（含剪枝）：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_set>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=100;
bool isPrime[maxn]; //假设都为质数
vector<int> ans;
bool isUsed[maxn];
int n; void getPrimeTable(){
memset(isPrime,1,sizeof(isPrime));
isPrime[0]=isPrime[1]=false;
for(int i=2;i<maxn;i++){
if(isPrime[i]){
for(int j=i+i;j<maxn;j=j+i){
isPrime[j]=false;
}
}
}
} void dfs(int index){
if(index>=n){
int temp=ans[0]+ans[index-1]; //判断第一个数和最后一个数之和
if(isPrime[temp]==false){
return;
}
for(int x:ans){
printf("%d ",x);
}
printf("\n");
return;
}
for(int i=2;i<=n;i++){
if(isUsed[i]==true) continue;
int temp=ans[index-1]+i;
if(isPrime[temp]==false) continue; //剪枝
ans.push_back(i);
isUsed[i]=true;
dfs(index+1);
ans.pop_back();
isUsed[i]=false;
}
} int main(){
getPrimeTable();
n=4;
ans.push_back(1);
dfs(1);
return 0;
}
实例五 N皇后问题：
实例六 求给定矩阵“块” 的个数：
给出一个m*n的矩阵，矩阵中的元素为0或1,。称位置(x,y)与其上下左右四个位置是相邻的。如果矩阵中有若干个1是相邻的（不必两两相邻），那么称这些1构成了一个“块”。求给定的矩阵中“块” 的个数。
样例输入：
6 7
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
样例输出：
4
题意理解：![深度优先搜索DFS（一）-LMLPHP]( "深度优先搜索DFS（一）-LMLPHP")
求如图所示“块”的个数
分析：首先想到的是DFS遍历所有顶点，标记已访问顶点，最终统计“块”个数。代码如下：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_set>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=100;
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};
struct node{
int x,y;
}Node;
int n,m; //¾ØÕó´óСΪn*m
int matrix[maxn][maxn];
bool inq[maxn][maxn]; bool judge(int x,int y){
if(x>=n||x<0||y>=m||y<0) return false;
if(matrix[x][y]==0||inq[x][y]==true) return false;
return true;
} void DFS(int u,int v){
inq[u][v]=true;
for(int i=0;i<4;i++){
int newX=u+X[i];
int newY=v+Y[i];
if(judge(newX,newY)){
inq[newX][newY]=true;
DFS(newX,newY);
}
}
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
scanf("%d%d",&n,&m);
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
scanf("%d",&matrix[x][y]);
}
}
int ans=0;
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
if(matrix[x][y]==1&&inq[x][y]==false){
ans++;
DFS(x,y);
}
}
}
printf("%d\n",ans);
return 0;
}
这里用到一个技巧就是：
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};
for(int i=0;i<4;i++){
int newX=u+X[i];
int newY=v+Y[i];
}
当矩阵过大时，DFS效率远不如BFS，下面给出BFS解法：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_set>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int maxn=100;
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};
struct node{
int x,y;
}Node;
int n,m;
int matrix[maxn][maxn];
bool inq[maxn][maxn]; bool judge(int x,int y){
if(x>=n||x<0||y>=m||y<0) return false;
if(matrix[x][y]==0||inq[x][y]==true) return false;
return true;
} void BFS(int x,int y){
queue<node> Q;
Node.x=x;
Node.y=y;
Q.push(Node);
inq[x][y]=true;
while(!Q.empty()){
node top=Q.front();
Q.pop();
for(int i=0;i<4;i++){
int newX=top.x+X[i];
int newY=top.y+Y[i];
if(judge(newX,newY)){
Node.x=newX,Node.y=newY;
Q.push(Node);
inq[newX][newY]=true;
}
}
}
} int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
scanf("%d%d",&n,&m);
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
scanf("%d",&matrix[x][y]);
}
}
int ans=0;
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
if(matrix[x][y]==1&&inq[x][y]==false){
ans++;
BFS(x,y);
}
}
}
printf("%d\n",ans);
return 0;
}
变式（BFS）：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_set>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int maxn=100;
struct node{
int x,y;
int step;
}S,T,Node;
int n,m;
char matrix[maxn][maxn];
bool inq[maxn][maxn]={false};
int X[4]={0,0,1,-1};
int Y[4]={0,0,1,-1}; bool judge(int x,int y){
if(x>=n||x<0||y>=m||y<0) return false;
if(matrix[x][y]=='*') return false;
if(inq[x][y]==false) return false;
return true;
} int BFS(){
queue<node> q;
q.push(S);
while(!q.empty()){
node top=q.front();
q.pop();
if(top.x==T.x&&top.y==T.y) return top.step; //到达终点，直接返回当前步数
for(int i=0;i<4;i++){
int newX=top.x+X[i];
int newY=top.y+Y[i];
if(judge(newX,newY)){
Node.x=newX,Node.y=newY;
Node.step=top.step+1;
q.push(Node);
inq[newX][newY]=true;
}
}
}
return -1;
} int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
getchar();
for(int j=0;j<m;j++){
matrix[i][j]=getchar();
}
matrix[i][m+1]='\0';
}
scanf("%d%d%d%d",&S.x,&S.y,&T.x,&T.y);
S.step=0;
printf("%d\n",BFS());
return 0;
}