回溯算法（排列、子集合、TSP、N后问题、0-1背包问题）

目录

一、排列

二、子集合

三、TSP问题

四、n皇后问题 

五、0-1背包问题

一、排列

1.设计算法从前m个大写字母(m<=26)种取出n个字母的所有排列（组合），并编程实现 

输入格式
输入M N
1<=M=26, N<=M  
输出格式
按字典序输出排列
注意：行末不输出多余空格 
样例
4  2
输出
A B
A C
A D
B A
B C
B D
C A
C B
C D
D A
D B
D C 
分析：1、选取n个数有cmn种选择，并且前后的选择不能重复
           2、设置标记数组flag标志被选过的数，再调用函数时不在选取

代码实现

#include
char a[26]; //用于存储前m个大写字母
int m,n;
int flag[26],ns[26];//标记数组，ns用于存放当前位置对应的字母
void serch(int c){//c表示当前位置为c 
	int i;
	if(c==n){
		for(i=0;i 
二、子集合 

 设集合S={x1,x2,…,xn}是一个正整数集合，c是一个正整数，子集和问题判定是否存在S的一个子集S1，使S1中的元素之和为c。试设计一个解子集和问题的回溯法
 
 
输入格式
 输入数据第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值
 接下来的1行中，有n个正整数，表示集合S中的元素
 n<10,c<100
输出格式
 输出所有满足条件的集合，当问题无解时，输出“No Solution!”。
 注意：末尾不输出多余空格
 按照输入顺序输出，比如第一个满足条件的子集合是[2 2 6]，那么就先输出它，子集合内的数也按照输入顺序输出
Sample Input
 5 10
 2 2 6 5 4  
Sample Output
 2 2 6
 6 4 
分析：1、子集合问题解空间类似二叉树
            2、设置标记数组，标记第i个位置是否进入解集，判断是否满足输出条件
            3、不满足则调用下一层数组i+1，对数字i取消标记，使其进入i+1，直到所有数字遍历完
代码实现
 
#include
#include
#include

const int N = 1000;//宏定义一个数表示数组的大小

int arr[N];//存储集合元素
bool ans[N];//标记是否进入集合
int ansum=0;//当前和
int num,sum;//num表示集合元素个数，sum表示目标和 

void serch(int n){
	if(n>num) return ;//遍历完没有满足条件的直接返回 
	ans[n]=true;
	ansum+=arr[n];//当前n对应的数字放入数字和
	
	if(ansum==sum){//算上当前n位置的数字，当前和等于目标和 
		int i;
		for(i=0;i 
三、TSP问题 
 
输入格式
 第一行输入n，代表有n个城市。
 接下来n行每行输入n个数，第i行j列的值代表i市到j市的距离，0代表城市之间不通
 注意：起点和终点都为1
 n<7,城市之间的距离都不超过10
输出格式
 第一行输出最少的旅行费用
 第二行输入旅行路径
 （保证只有一条最短旅行路径）
Sample Input
 4  
 0 30 6 4
 30 0 5 10
 6 5 0 20
 4 10 20 0  
 
Sample Output
 25
 1 3 2 4 1
分析：要找费用最少的路径，对于第i个位置到第j个位置将进行判断
         1、路径是否连通
         2、加入该条路径后费用是否是当前最优
         3、因此，需要两个数组，一个存放路径，一个作为标记
 
代码实现
 
#include
int n;
const int N = 7;//宏定义N用于表示数组的大小

int a[N][N];//记录各城市之间的距离
int bestr[N];//记录最短路径的位置顺序
int sum=0,r[N];//当前路径长度，当前路径顺序
int bestsum=1000;//定义最短路径长度
int flag[N];//标记数组
void serch(int num){//num表示当前第几个位置 
	flag[1]=1;
	if(num>n){//当前位置到了n+1个，回到原点 
		if(a[r[num-1]][r[1]]&&(sum+a[r[num-1]][r[num]]=2;i--){
			if(flag[i]==0){
				r[num]=i; 	//将地点i赋给r[num],当前第num个位置选择的地点是i 
				flag[i]=1;	//标记地点i已被遍历 
				//判断上个位置到当前位置是否连通，并判断当前当前路径和是否小于最小路径和 
				if((a[r[num-1]][r[num]])&&(sum+a[r[num-1]][r[num]] 
四、n皇后问题  
问题描述
 
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
 你的任务是，对于给定的N，求出有多少种合法的放置方法。
 
输入格式
 
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
 
输出格式
 
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
 
Sample Input
 
1 8
 5 0
 
Sample Output
 
1 92
 10
 
分析
 
重点：考虑如何实现不在同一斜线
       1、判断方式:两个皇后的坐标(i,j),(k,l)
       2、|i-k|==|j-l|则在同一斜线上
       3、从第0行到第n行，每行放一个皇后
       4、用标记数组flag[i]标记放过的位置 i
代码实现
 
#include
#include
#define N 10

int n,sum=0;//n个皇后，共有sum中放法
int x[N];//记录皇后放置的列位置
int ok;
int flag[N];//标记放过的位置

void serch(int t){//t表示当前行位置，从第0行开始到n-行
	if(t==n){//放到n-1行 
		sum++;//放到最后一个，方法加1 
	} 
	else{
		for(int i=0;i 
五、0-1背包问题  
任务描述
 
 
输入格式
 
第一行输入n，c，分别代表物品的数量和背包的容量
 第二行输入n个数 分别代表每个物品的重量
 第三行输入n个数，分别代表每个物品的价值
 1 
输出格式
 
输出一个数，代表能装入的最大价值
 
Sample Input
 
4 7
 3 5 2 1
 9 10 7 4
 
Sample Output
 
20
 
分析
 
 0-1背包问题的解空间可以用子集树表示。解0-1背包问题的回溯法与解装载问题的回溯法十分相似 
 在搜索解空间树时，只要其左儿子节点是一个可行的节点，搜索就进入其左子树;
 而当右子树中有可能包含最优解时才进入右子树搜索，否则将右子树剪去
 设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r<=bestp时，可剪去右子树
 对于0-1背包问题，可用一颗完全二叉树表示其解空间
 
代码实现
 
#include 
#define N 100
int n,c;//物品数量和背包容量
int w[N],v[N];//物品重量、价值
int bestsum=0,sum=0,ww=0;//最大价值、当前价值、当前背包里物品重量
int flag[N]={0};
int x[N];//标记进入左右分支 

void serch(int i){//表示第i个物品 
	if(i>=n){
		if(bestsum