1.排列
任务描述
1.设计算法从前m个大写字母(m≤26)种取出n个字母的所有排列（组合），并编程实现
输入格式
输入M N
1<=M=26, N<=M
输出格式
按字典序输出排列
注意：行末不输出多余空格
Sample Input
4 2
Sample Output
A B
A C
A D
B A
B C
B D
C A
C B
C D
D A
D B
D C
思路：使用一个标记数组’flag’来表示已经使用过的字母，再次调用回溯函数时已经被标记的字母将不被选中
#include"stdio.h"
char a[26];
int m,n;
int flag[26],ans[26];
void search(int c){
int i;
if(c==n){
for(i=0;i<n-1;i++) printf("%c ",a[ans[i]]);
printf("%c\n",a[ans[i]]);
}
else{
for(int i=0;i<m;i++){
if(flag[i]) continue;
ans[c]=i; //存放当前c位置对应的字母(0~m)
flag[i]=1; //当前字母做标记，表示已被引用
search(c+1);
flag[i]=0;
}
}
}
int main(int argc, const char** argv) {
scanf("%d%d",&m,&n);
for(int i=0;i<26;i++) a[i]='A'+i;
search(0);
return 0;
}
2.子集合
任务描述
设集合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
思路：同样是使用标记数组，这里用bool vis[N]来标记当前数字i是否被记入，对数字i进行标记和不标记，类似于二叉树，被标记的数字i计入数字和，判断当前数字和是否满足输出条件，不满足则调用下一层数字i+1。对数字i取消标记，使其进入下一层数字i+1,并对i+1进行标记和不标记两种处理方式，直到所有数字遍历完。
#include"stdlib.h"
#include"string.h"
#include "stdio.h"
const int N = 1000;
int arr[N]; // 存储几何元素
bool vis[N]; // 存储集合状态
int valSum=0; //当前和
int num,sum;
void search(int n){//n是当前数字所在位置\
//遍历完没有合适的数字
if(n>num) return ;
//当前n对应数字放入数字和
vis[n]=true;
valSum +=arr[n];
//满足数字和条件
if(valSum==sum)//算上当前n位置的数字，数字和等于sum
{
int i;
for(i=0;i<n;i++){
if(vis[i]) printf("%d ",arr[i]);
}
printf("%d\n",arr[i]);//n位置的数字
}
else if(valSum<sum)//当前数字和小于sum，说明可以再加数字个数
{//当前n的标记继续存在
search(n+1);
}
//回溯下一个位置的数字
vis[n]=false;//取消当前n的标记
valSum -= arr[n];
search(n+1);
return ;
}
int main(int argc, char const *argv[])
{
scanf("%d%d",&num,&sum);
for(int i=0;i<num;i++){
scanf("%d",&arr[i]);
}
search(0);
return 0;
}
3.TSP问题
务描述
输入格式
第一行输入n，代表有n个城市。 接下来n行每行输入n个数，第i行j列的值代表i市到j市的距离，0代表城市之间不通 注意：起点和终点都为1 n<7,城市之间的距离都不超过100
输出格式
第一行输出最少的旅行费用 第二行输入旅行路径 （保证只有一条最短旅行路径）
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
思路：用一个数组存放当前走过的地点的路径x[],记录下当前路径的长度，建立标记数组flag[],如果当前地点被标记，则下轮选地点时不会选被标记的地点。截止条件为走过了n个地点要回到原点，回溯判断条件为上一个地点到当前选用的地点是否有路径，算上上一个地点到当前选用的地点的路径记为走过的总路径，判断当前走过的总路径是否超过了当前最短总路径。
#include"stdio.h"
int n;
const int N = 7;
int a[N][N];//记录初始各个位置间的距离
int bestr[N];//定义最短路径的位置顺序
int bestsum=999;//定义最短路径的长度
int sum=0,r[N];//定义当前路径的长度、路径顺序
int flag[N];
void search(int num){//num表示当前第几个位置
flag[1]=1;
//当前位置到了第n+1个，回到原点
if(num>n){
if((a[r[num-1]][r[1]])&&(sum+a[r[num-1]][r[num]]<bestsum)){
bestsum=a[r[num-1]][r[1]]+sum;
for(int i=1;i<=n;i++) bestr[i]=r[i];
}
}
else
{
for(int i=n;i>=2;i--){
if(flag[i]==0){
r[num]=i; //将地点i赋给r[num]，当前第num个位置选择的地点是i
flag[i]=1; //将地点i标记，下次遍历排除i
if((a[r[num-1]][r[num]])&&(sum+a[r[num-1]][r[num]]<bestsum)){//判断上个位置到当前位置这两个地点的距离是否为0，并判断当前路径和是否大于最小路径和
sum += a[r[num-1]][r[num]];
search(num+1);
sum -= a[r[num-1]][r[num]];
}
flag[i]=0;
}
}
}
}
int main(int argc, const char** argv) {
scanf("%d",&n);
for(int i=0;i<=n;i++){
r[i]=i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
search(2);//第一个位置直接连接第二个位置
printf("%d\n",bestsum);
for(int i=1;i<=n;i++) printf("%d ",bestr[i]);
printf("1");
return 0;
}
4.n皇后问题
任务描述
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法。
输入格式
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
输出格式
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1 8 5 0
Sample Output
1 92 10
思路：重点是判断是否在同一斜线上，判断方式为两个皇后坐标(i,j) (k,l),绝对值：|i-k|==|j-l|,则在同一斜线上。皇后不可以再同一行，那么我们可以从第0行开始走到第n行，每行放一个皇后。用标记数组flag[]记录当前放过的皇后的位置i，将flag[i]标为1，用来排除列。
#include"stdio.h"
#include"math.h"
#define N 10
int n,sum=0;//n皇后，n*n棋盘，共有sum种放置方法
int x[N];//记录皇后放置的列位置
int ok;
int flag[N];
void search(int t){//t表示当前行位置，从第0行开始放置皇后，放到第n-1行
if(t==n)//皇后在n-1行
{
sum++;//成功放置n皇后，总数加一
// for(int i=0;i<n;i++) printf("%d ",x[i]);
// printf("\n");
}
else
{
for(int i=0;i<n;i++){//皇后放在第i，皇后的位置为t行i列
if(flag[i]==0){//不和之前的皇后在同一行
ok=1;
for(int j=0;j<t;j++){
if(abs(t-j)==abs(i-x[j])){//和之前的皇后在同一列
ok=0;
break;
}
}
if(ok){
x[t]=i;
flag[i]=1;
search(t+1);
flag[i]=0;
}
}
}
}
}
int main(int argc, char const *argv[])
{
scanf("%d",&n);
while(n)
{
search(0);
printf("%d\n",sum);
sum=0;
scanf("%d",&n);
}
return 0;
}
5.0-1背包
任务描述
输入格式
第一行输入n，c，分别代表物品的数量和背包的容量 第二行输入n个数 分别代表每个物品的重量 第三行输入n个数，分别代表每个物品的价值 1<n<100,1<c<100,重量不超过100，价值不超过1000
输出格式0
输出一个数，代表能装入的最大价值
Sample Input
4 7 3 5 2 1 9 10 7 4
Sample Output
20
思路：类似于上面第二题的子集和，要对每个物品进行0、1处理，1表示将其放入背包，如果放入背包总重量和超重，则不将其放入
#include "stdio.h"
#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 backtrack(int i){//t表示第t个物品
if(i>=n){
if(bestsum<sum) bestsum=sum;
return ;
}
else if(ww+w[i]<=c)//进入右孩子
{
x[i]=1;
ww+=w[i];
sum+=v[i];
backtrack(i+1);
ww-=w[i];
sum-=v[i];
}
//进入左孩子,必须进入
x[i]=0;
backtrack(i+1);
return ;
}
int main(int argc, char const *argv[])
{
scanf("%d%d",&n,&c);
for(int i=0;i<n;i++) scanf("%d",&w[i]);
for(int i=0;i<n;i++) scanf("%d",&v[i]);
backtrack(0);
printf("%d",bestsum);
return 0;
}