【C++】回溯算法基础入门

本文主要是介绍【C++】回溯算法基础入门，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简介

回溯算法基于深度优先搜索，实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
由于非递归式回溯算法较难实现，本文只介绍递归式回溯。

回溯算法框架

int a[n+1];//这里用下标1~n
void DFS(int i){//搜索第i层if(i>n){//搜索结束//结果处理(输出结果,方案计数等)}for(int j=下界;j<=上界;j++){if(限界函数&&约束条件){//满足限界函数和约束条件x[i]=j;//保存当前层的结果...//回溯入场准备工作DFS(i+1);//搜索下一层...//回溯退回清理工作}}
}

例题

打靶问题

题目描述

一个人打 $10$ 次靶（范围在 $0$ 环到 $10$ 环），问这 $10$ 次打靶之后，共中 $90$ 环的情况的个数。

输入格式

无

输出格式

输出中 $90$ 环的个数。

样例

无

参考题解

#include <iostream>
using namespace std;
int cnt=0;
void DFS(int k,int v){//k表示打第i次靶,v表示前i-1次靶得分 if(k==10){if(v+10>=90)//第10环满分,总分大于等于90说明有解 cnt++;//结果+1 return;}for(int i=0;i<=10;i++){//枚举第i次打靶得分 if(v+i+10*(10-k)>=90){//如果后面几次都得满分达到90分才有解 DFS(k+1,v+i);//搜索k+1层,更新得分v+i }}
}
int main(){DFS(1,0);cout<<cnt;//输出方案数 return 0;
}

全排列1

题目描述

从 $n$ 个不同元素中任取 $m (m \leq n)$ 个元素，按照一定的顺序排列起来，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列。

输入格式

一行一个正整数 $n$ .

输出格式

输出所有排列，每个数字之间以空格隔开，每个结果之间以换行隔开。

样例输入

样例输出

数据范围与提示

$1\le n \le 7$

参考题解

#include <iostream>
using namespace std;
int x[8],n;
void DFS(int k){//k表示第k个数的搜索 if(k>n){//搜索结束,输出x[]数组 for(int i=1;i<=n;i++){printf("%d ",x[i]);}printf("\n");return;}for(int i=1;i<=n;i++){//枚举x[k] x[k]=i;//标记x[k]=i DFS(k+1);//搜索下一层 }
}
int main(){cin>>n;DFS(1);return 0;
}

全排列2

题目描述

把 $1\sim n$ 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数 $n$ 。

输出格式

按照从小到大的顺序输出所有方案，每行 $1$ 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

输入样例

输出样例

数据范围与提示

$1\le n \le 9$

参考题解

#include <iostream>
#include <algorithm>
using namespace std;
int x[10],visit[10],n;
void DFS(int k){//k表示第k个数的搜索 if(k>n){//搜索结束,输出x[]数组 for(int i=1;i<=n;i++){printf("%d ",x[i]);}printf("\n");return;}for(int i=1;i<=n;i++){//枚举x[k]if(!visit[i]){//如果i未被访问 x[k]=i;//标记x[k]=ivisit[i]=1;//i标记1表示访问了 DFS(k+1);//搜索下一层visit[i]=0;//回溯回退,标记i为0表示访问 } }
}
int main(){fill(visit,visit+10,0);//标记visit为0表示未访问 cin>>n;DFS(1);return 0;
}

组合的输出

题目描述

排列与组合是常用的数学方法，其中组合就是从 $n$ 个元素中抽出 $r$ 个元素(不分顺序且 $r\le n$ )，我们可以简单地将n个元素理解为自然数 $1,2,\dots ,n$ ，从中任取 $r$ 个数。
现要求你用递归的方法输出所有组合。
例如 $n = 5, r = 3$ ，所有组合为：

参考题解

#include <iostream>
#include <algorithm>
using namespace std;
int x[21],visit[21],n,r;
void DFS(int k){//k表示第k个数的搜索 if(k>r){//搜索结束,输出x[]数组 for(int i=1;i<=r;i++){printf("%d ",x[i]);}printf("\n");return;}for(int i=x[k-1]+1;i<=n;i++){//枚举x[k],输出组合数不能有重复,当x[i]>x[i-1]时保证无重复if(!visit[i]){//如果i未被访问 x[k]=i;//标记x[k]=ivisit[i]=1;//i标记1表示访问了 DFS(k+1);//搜索下一层visit[i]=0;//回溯回退,标记i为0表示访问 } }
}
int main(){x[0]=0;//为了方便下界使用,见DFS第二个for循环fill(visit,visit+21,0);//标记visit为0表示未访问 cin>>n>>r;DFS(1);return 0;
}

排列的生成

题目描述

给出 $n$ 和 $m$ ，请编程按字典序输从 $1,2,\dots ,n$ 中选择 $m$ 个数的所有排列。

输入格式

一行包含两个整数 $n, m$ ，两个整数之间用一个空格分开。

输出格式

按字典序输出所有可能的排列，每个排列输出一行，元素之间用一个空格分开。

样例输入

3 2

样例输出

数据范围与提示

$1\le m \le n \le 11$

#include <iostream>
#include <algorithm>
using namespace std;
int visit[12];//标记访问 
int num[12];//标记存储 
int n,m;//n的m排列 
void DFS(int k){if(k==m+1){//输出当前方案 for(int i=1;i<=m;i++){cout<<num[i]<<' ';}cout<<endl;return;}for(int i=1;i<=n;i++){//查找可选值 if(!visit[i]){//可选 visit[i]=1;//标记已选 num[k]=i;//记录已选 DFS(k+1);//搜索下一层 visit[i]=0;//回退,标记未选 }}
}
int main(){cin>>n>>m;fill(visit,visit+12,0);//访问标0 DFS(1);//调用回溯 return 0;
}

工作分配

题目描述

有 $n$ 项工作要分配给 $m$ 个人完成，每个人只能从事一项工作，且每项工作只能由一人完成。已知第 $i$ 个人完成第 $j$ 项工作的工费是 $c [i] [j]$ 元，那么怎么给每个人分配工作才能使得总工费最小。

输入格式

一个整数 $n$ ，接下来的 $n$ 行，每行一个 $10000$ 以内的正整数，其中第 $i + 1$ 行第 $j$ 列的整数 ,表示第 $i$ 个人完成第 $j$ 项工作时的工费。

输出格式

输出一个整数，表示最小的总工费。

样例输入

样例输出

数据范围与提示

$\le n \le 20$

#include <iostream>
#include <algorithm>
using namespace std;
int visit[21];//标记访问
int num[21][21];//工费矩阵
int preCost[21];//第i~n个员工的最小花费和 
int n;
int cost=1e9;//初始化最小花费为无限大
void DFS(int curCost,int index){//curCost,index分别表示index-1层花费和index层if(index>n){//递归边界 cost=min(cost,curCost);//更新花费 return;//回退 }for(int i=1;i<=n;i++){if(!visit[i]&&curCost+num[index][i]+preCost[index+1]<cost){//未访问,且最小花费小于当前值 visit[i]=1;DFS(curCost+num[index][i],index+1);//更新花费,搜索下一层 visit[i]=0;}}
}
int main(){scanf("%d",&n);//输入n for(int i=1;i<=n;i++){visit[i]=0;//标记未访问 preCost[i]=1e9;for(int j=1;j<=n;j++){scanf("%d",&num[i][j]);//输入花费preCost[i]=min(preCost[i],num[i][j]);}}preCost[n+1]=0;//为了方便计算 for(int i=n-1;i>=1;i--) preCost[i]+=preCost[i+1];//计算i~n的最小花费 DFS(0,1);printf("%d",cost);//输出最小花费 return 0;
}

方格填数

题目描述

在 $n * n$ 的棋盘上，填入 $1,2,\dots ,n*n$ 共 $n * n$ 个数，使得任意两个相邻的数之和为素数。例如：
请添加图片描述

在这里我们约定：左上角的格子里必须填数字 $1$ 。

输入格式

一行一个整数： $n$ 。

输出格式

输出解时按行从上到下，每行从左到右依次输出。如有多种解，则输其中字典序由小到大的前三个解，若不足三个，则按字典序全部输出，如果无解，则输出 $0$ 。

样例输入

样例输出

1 2 11 12
4 9 8 5
7 10 3 14
6 13 16 151 2 11 12
4 9 8 5
13 10 3 14
6 7 16 151 2 11 12
4 15 8 5
7 16 3 14
6 13 10 9

数据范围与提示

$1\le n\le 10$

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 11
using namespace std;
int mp[N][N];//方案值存取 
int visit[N*N];//访问标记 
int isPrime[101];//素数标记 
int n,k=0;//n表示n*n矩阵,k表示解的个数 
void init(){//素数打表fill(isPrime,isPrime+101,0);int num[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};for(int i=0;i<25;i++) isPrime[num[i]]=1;
}
void show(){//输出矩阵 for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){printf("%d ",mp[i][j]);}printf("\n");}printf("\n");k++;//记录方案数+1 
}
int test(int x,int y,int i){//试探i能不能放在(x,y) 
//每一个需要满足左边和上边的加起来是素数 if(x>1&&isPrime[mp[x-1][y]+i]==0)return 0;if(y>1&&isPrime[mp[x][y-1]+i]==0)return 0;return 1;
}
void DFS(int x,int y){if(k==3)//找到3个解了,停止搜索 return;if(x==n+1){//搜索边界,满足要求 show();//输出矩阵 return;}if(x==1&&y==1){//(1,1)固定是1 mp[x][y]=1;DFS(1,2);return; }for(int i=2;i<=n*n;++i){//否则从2开始放置 if(!visit[i]){//未访问 mp[x][y]=i;//记录i visit[i]=1;//标记访问 if(test(x,y,i)){//检测可否放置 if(y==n)//到了最后一列 DFS(x+1,1);//搜索下一行第一列 elseDFS(x,y+1);//搜索本行下一列 }visit[i]=0;//回退标记未访问 }}
}
int main() {init();//生成素数表 cin>>n;k=0;mp[1][1]=1;//1号是1 fill(visit,visit+N*N,0);if(n!=1)//不等于1才有解 DFS(1,1);//从(1,1)开始搜索 if(k==0)//方案数为0 printf("0\n");return 0;
}

回文数(难题)

题目描述

“回文数” 则是有类似 $22, 383, 5445, 12321$ 这些数，不论是从左向右顺读，还是从右向左倒读，结果都是一样的。
请编程找出区间 $[a, b]$ 范围内的所有回文数。

输入格式

第 $1$ 行一个整数 $n$ ，表示数据组数；
接下来的 $n$ 行，每行两个整数 $a, b$ ，表示区间 $[a, b]$ 。

输出格式

输出 $[a, b]$ 区间内的回文数的数目。

输入样例

3
1 100
100 1000
873 1762810749

输出样例

18
90
117531

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
string tmp;
string itos(ll n){//数字转字符串 string s;do{s=char(n%10+'0')+s;n/=10;}while(n);return s;
}
ll pow(ll a,ll b){//快速幂 if (b<0)return 0;ll sum=1;while(b){if(b&1)sum*=a;a*=a;b>>=1;}return sum;
}
ll len(ll n){//数的位数if(n==0)return 1;ll len=0;while(n){len++;n/=10;}return len;
}
ll calc(ll k){//计算k位回文数个数if(k==1)return 10;//1位全是 if(k==2)return 9;//2位的有11,22,...,99 if(k%2==1)return 9*pow(10,k/2);//奇数个,首尾9种,其余位10种 elsereturn 9*pow(10,k/2-1);//偶数个,首尾9种,其余位10种 
}
void DFS(string b,ll r,ll k,ll &cnt){//计算小于等于b的l位回文数个数,l是b的长度,k是搜索第k层 if(k!=0&&tmp.substr(0,k)>b.substr(0,k))return;if(tmp.substr(0,k)<b.substr(0,k)){//临时数前缀比b小后面的位数不管了cnt+=pow(10,(r+1)/2-k);return;}if(k>=(r+1)/2){if(tmp<=b)cnt++;return;}for(ll i=0+(k==0);i<=9;i++){tmp[k]=tmp[r-1-k]=char('0'+i);DFS(b,r,k+1,cnt);}
}
ll solve(ll s) {//[0,s]回文数个数ll sum=0;for(int i=1;i<len(s);i++) sum+=calc(i);//小于s长度的回文串个数 tmp.resize(len(s));//改变长度 DFS(itos(s),len(s),0,sum);//搜索s等长回文串个数 return sum;
}
int main(){ll n,a,b;cin>>n;while(n--){cin>>a>>b;cout<<solve(b)-solve(a)<<endl;}
}

##　选数

题目描述

已知 $n$ 个整数，以及一个整数 $m$ 。从 $n$ 个整数中任选 $m$ 个整数相加，可分别得到一系列的和。例如当 $n = 4, m = 3$ ，四个整数分别为 $3, 7, 12, 19$ 时，可得全部的组合与它们的和为：
$3+7+12=22\\ 3+7+19=29\\ 7+12+19=38\\ 3+12+19=34$
现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：
$3 + 7 + 19 = 29$ 。

输入格式

第 $1$ 行包含两个正整数 $n$ 和 $m$ ；
第 $2$ 行有 $n$ 个正整数： $x_1,x_2,\dots ,x_n$ 。

输出格式

一个整数，为答案。

输入样例

4 3
3 7 12 19

输出样例

数据范围与提示

$1\le k < n \le 25\\ 1\le x_i \le 500000$

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 26
using namespace std;
int x[N];
int mp[N];
int visit[N];
int n,m,total=0;
int isPrime(int k){//试探法求素数,优化效率可采用埃氏筛法或欧拉筛法 if(k==2)return 1;if(k<=1||k%2==0)return 0;for(int i=3;i*i<=k;i+=2){if(k%i==0)return 0;}return 1;
}
void solve(int k,int sum){//搜索第k层,sum是k-1层的和 if(k==m+1){//递归尽头 if(isPrime(sum))//是素数 total++;return;}for(int i=mp[k-1]+1;i<=n;i++){//因为是组合,所以要从上个数+1开始找,避免重复 if(!visit[i]){visit[i]=1;mp[k]=i;solve(k+1,sum+x[i]);//更新和,搜索下一层 visit[i]=0;}}
}
int main(){mp[0]=0;cin>>n>>m;for(int i=1;i<=n;i++) cin>>x[i];solve(1,0);cout<<total;return 0;
}

0/1背包问题

题目描述

有 $n$ 种物品，每种物品只有 $1$ 个。第 $i$ 种物品的体积为 $v [i]$ ，价值为 $p [i]$ 。选一些物品装入一个容量为 $C$ 的背包，使得背包内物品在总体积不超过 $C$ 的前提下价值尽量大。

输入格式

第 $1$ 行包含两个正整数 $C$ 和 $n$ ；接下来的 $n$ 行，每行两个整数： $v [i]$ 和 $p [i]$ ，表示第 $i$ 种物品的体积和价值。

输出格式

一个整数，为答案。

输入样例

输出样例

数据范围与提示

$1\le n\le 30\\ 1\le v[i]\le C \le 1,000,000,000\\ 1\le p[i]\le ,000,000$

#include <iostream>
#include <algorithm>
using namespace std;
int C,n;//最大容量和背包数 
int mCost=0;//最大价值 
int v[31],p[31];//体积和价值
int preCost[32];//计算i~n的价值和 
void DFS(int k,int vNow,int pNow){//选第k个,当前花费if(k==n+1){//回溯边界 mCost=max(mCost,pNow);return;}//预测一下preCost取最大时能否超过当前和,不能就不必搜索 if(vNow+v[k]<=C&&pNow+p[k]+preCost[k+1]>=mCost) DFS(k+1,vNow+v[k],pNow+p[k]);//装k号背包 if(vNow<=C&&pNow+preCost[k+1]>=mCost) DFS(k+1,vNow,pNow);//不装k号背包 
}
int main(){cin>>C>>n;for(int i=1;i<=n;i++){cin>>v[i]>>p[i];preCost[i]=p[i];}for(int i=n-1;i>=1;i--) preCost[i]+=preCost[i+1];//记录i~n的价值和 preCost[n+1]=0;//方便计算 DFS(1,0,0);cout<<mCost;return 0;
}

放棋子

题目描述

给出一个 $n * m$ 的棋盘，要在棋盘上放 $c$ 个棋子，使得任意两个棋子不相邻（上下左右）。问有多少种方案。比如 $2 * 3$ 的棋盘上放 $2$ 个棋子有如下 $8$ 种合法方案。
请添加图片描述

输入格式

一行包含三个整数。

输出格式

一个整数，表示方案数。

输入样例

2 3 2

输出样例

数据范围与提示

$0<n,m\le 20且n*m\le 50$

#include <iostream>
#include <algorithm>
#define N 21
using namespace std;
bool mp[N][N];
int n,m,c;
int total=0;
int test(int x,int y){//测试x,y能否放棋子if(y>1&&mp[x][y-1]==1)return 0;  //上方有棋子if(x>1&&mp[x-1][y]==1)return 0;  //左方有棋子return 1;
}
void DFS(int x,int y,int sum){//从x,y开始,已经放了sum个棋子if(sum==c){//放满了 total++;return;}if(y==m+1){//下一列x++;y=1;}if(x>n||sum+1+((n*m-(x-1)*m-y)+1)/2<c)return;//超出范围或放不下 mp[x][y]=1;if(test(x,y)) DFS(x,y+1,sum+1);//放了搜索下一层 mp[x][y]=0; DFS(x,y+1,sum);//不放搜索下一层
}
int main(){fill(mp[0],mp[0]+N*N,0);cin>>n>>m>>c;DFS(1,1,0);cout<<total;return 0;
}

数的划分

题目描述

将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两份不能相同(不考虑顺序)。

例如： $n = 7, k = 3$ ，这三种分法： $7 = 1 + 1 + 5; 7 = 1 + 5 + 1; 7 = 5 + 1 + 1$ 被认为是相同的。

给出 $n$ 和 $k$ ，请编程输出前 $100$ 个不同的分法。

输入格式

一行包含两个整数： $n, k$

输出格式

输出前 $100$ 个的不同分解方法，格式见样例，按分解称的 $k$ 个数排列的字典序输出。最后一行输出方案总数

样例例入

7 3

样例输出

7=1+1+5
7=1+2+4
7=1+3+3
7=2+2+3
4

数据范围与提示

$1<n\le 200\\ 1\le k\le 8$

#include <iostream>
#include <algorithm>
#define N 201
using namespace std;
int n,m;
int num[N];
int total=0;
void DFS(int remind,int k){//剩余数remind拆分,回溯层数为kif(k==m){num[k]=remind;//最后一个就是remind if(total<100){//小于100就输出方案数printf("%d=",n);for(int i=1;i<=m;i++) {printf("%d",num[i]);if(i!=m)printf("+");}printf("\n");}total++;//方案数+1 return;}for(int i=num[k-1];(m-k)*i<=remind-i;i++){//避免重复,num[k]需要大于等于num[k-1] num[k]=i;DFS(remind-i,k+1);}
}
int main(){scanf("%d%d",&n,&m);num[0]=1;DFS(n,1);printf("%d",total);return 0;
}

n皇后问题

题目描述

在 $n * n$ 格的国际象棋上摆放 $n$ 个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。请编一个程序找出 $n$ 皇后的所有解。

输入格式

一行一个整数 $n$ 。

输出格式

按题目所说的序列方法输出，解按字典顺序排列。请输出前 $3$ 个解(不足 $3$ 个就全部输出)。最后一行是解的总个数。

样例例入

样例输出

2 4 1 3
3 1 4 2
2

样例输出种序列 $2\ 4\ 1\ 3$ ，第 $i$ 个数表示在第 $i$ 行的相应位置有一个棋子。这是 $4$ 皇后问题的一个解。

#include <iostream>
#include <algorithm>
#define N 100
using namespace std;
int num[N];
bool visit[N];
int L[N],R[N];  //左右斜对角线
int n;
int total=0;
bool test(int x,int y){//测试斜对角线int l=x-y+n,r=x+y;if(L[l]||R[r])return 0;visit[y]=1;L[l]=1;//放置后标记左斜对角线 R[r]=1;//放置后标记右斜对角线return 1;
}
void reset(int x,int y){//回退重置斜对角线 int l=x-y+n,r=x+y;visit[y]=0;L[l]=0;R[r]=0;
}
void DFS(int i){//放第i行if(i==n+1){if(total<3){for(int i=1;i<=n;i++) printf("%d ",num[i]);printf("\n");}total++;}for(int j=1;j<=n;j++){if(!visit[j]&&test(i,j)){//测试i行放到j列visit[j]=1;num[i]=j;DFS(i+1);reset(i,j);//回退重置斜对角线}}
}
int main(){scanf("%d",&n);DFS(1);printf("%d",total);return 0;
}

迷宫问题

题目描述

一个网络迷宫有 $m$ 行 $n$ 列的单元格组成，每个单元格要么是空地(用 $1$ 表示)，要么是障碍物(用 $0$ 表示)。在迷宫中行走时，每一步只能上下左右移动到相邻的格子中，且任何时候都不能在障碍格中，也不能走道迷宫之外。起点和终点保证是空地。
请你编程找到一条从起点到终点移动步数最少的路线。

输入格式

第 $1$ 行包含两个整数 $m$ 和 $n$ ，表示迷宫是 $m$ 行 $n$ 列。

接下来的 $m$ 行每行包含长度为 $n$ 的 $01$ 串，

其中第 $i + 1$ 行的第 $j$ 个字符是’0’，表示迷宫的第 $i$ 行,第 $j$ 列是障碍物，是’1’表示迷宫的第 $i$ 行第 $j$ 列是空地。

最后一行包含四个整数： $s x, s y, e x, e y$ ， $(s x, s y)$ 表示起点行号和列号， $(e x, e y)$ 表示终点的行号和列号。

注意：迷宫的行号和列号编号都是从 $1$ 开始的。

输出格式

第一行一个整数，表示最少的移动步数，若无解，则输出"None."。

#include <iostream>
#include <algorithm>
#define N 26
using namespace std;
char graph[N][N];
bool visit[N][N];
int dist[2][4]={{-1,1,0,0},{0,0,-1,1}};//上下左右走法的加减值 
int m,n,ex,ey;
int mCost=626;//最少步数标记 
bool canVisit(int x,int y,int cost){//可以走 if(visit[x][y]) return 0;//未走过 if(x<1||y<1||x>m||y>n) return 0;//超出边界 if(graph[x][y]=='0') return 0;//墙 if(cost+abs(x-ex)+abs(y-ey)>mCost) return 0;//步数预测,走直线最短,如果可走 return 1;
}
void DFS(int x,int y,int cost){//当前在(x,y),到达(x,y)之前步数为cost if(x==ex&&y==ey){//到了终点 mCost=min(cost,mCost);return;}visit[x][y]=1;for(int i=0;i<4;i++){//走上下左右 int p=x+dist[0][i],q=y+dist[1][i];if(canVisit(p,q,cost+1)){DFS(p,q,cost+1);}}visit[x][y]=0;
}
int main(){int x,y;scanf("%d%d\n",&m,&n);for(int i=1;i<=m;++i){for(int j=1;j<=n;++j){scanf("%c",&graph[i][j]);}scanf("\n");}scanf("%d%d%d%d",&x,&y,&ex,&ey);DFS(x,y,0);if(mCost!=626)printf("%d",mCost);elseprintf("None.");return 0;
}

配对

题目描述
有 $n$ 个元素（ $n$ 是偶数）,依次编号为 $1,2,\dots ,n$ ，现在要把它们配成 $n / 2$ 对，其中第 $i$ 个元素与第 $j$ 个元素配对的代价是 $a [i] [j]$ （保证 $a [i] [j] = a [j] [i]$ ，且 $a [i] [i] = 0$ ），那么所有元素配对的最小代价是多少？

输入格式

第 $1$ 行为 $n$ ，表示有 $n$ 个元素。

接下来的 $n$ 行，每行 $n$ 个整数，表示 $n * n$ 的矩阵，其中矩阵的第 $i$ 行第 $j$ 列的整数表示 $a [i] [j]$ 。

输出格式

一个整数，表示最小代价。

输入样例

4
0 100 5 100
100 0 100 11
5 100 0 100
100 11 100 0

输出样例

数据范围与提示

$2\le n\le 18$

#include <iostream>
#include <algorithm>
#define N 20
#define INF 999999
using namespace std;
int n;
int costM[N][N];//匹配花费矩阵 
int visit[N];//访问向量 
int mCost=INF;//最小花费 
int preCost=INF;//costM最小值
void DFS(int pre,int k,int cost){//配对第k对,pre是第k-1对较小值,cost是前k-1对和int i;for(i=pre+1;i<n&&visit[i];i++);//从pre+1开始放置避免重复,找到一个未被访问的i visit[i]=1;for(int j=i+1;j<=n;j++){//j从i+1开始,保证配对i<j避免重复 if(!visit[j]&&cost+costM[i][j]+(n/2-k)*preCost<mCost){//未访问j且最小花费小于当前花费 visit[j]=1;if(k!=n/2) DFS(i,k+1,cost+costM[i][j]);//更新花费,搜索下一层else mCost=min(mCost,cost+costM[i][j]);//配对结束visit[j]=0;}}visit[i]=0;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&costM[i][j]);//输入 if(i!=j) preCost=min(preCost,costM[i][j]);//记录costM[i][j]最小值 }}DFS(0,1,0);printf("%d",mCost);return 0;
}