回溯法

程序员文章站 2022-07-12 10:08:08

...

一、概述

1、概念

回溯法有“通用解题法”之称。用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。

当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

2、注意

（1）为什么有的回溯是0到N-1，有的是1到N

第一种情况数组下标一般从0开始，第二种一般从1开始（推荐）

（2）对于层数不确定或条件复杂的，最好用非回溯做

如不连续的和条件

（3）为什么不用广度优先

https://mp.weixin.qq.com/s/ClKJXdyFeSSW0A8FLFksnA

3、解题思路

（1）针对所给问题，定义易于搜索的解空间；

（2）以深度优先方式搜索解空间

（3）在搜索过程中对每一步用**剪枝函数（判断条件：可以放吗？值符合条件吗？）**避免无效搜索。

4、技巧

（1）当情况比较复杂时，要学会自己处理：如使用数组等

（2）当起点确定时，从第二层开始，但要注意数组起点的初始化

二、子集树问题

1、概念

当所给问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间树称为子集树。

这类子集树通常有2^{n个叶结点，其结点总个数为2}(n+1)-1。遍历子集树的算法需Ω(2^n)计算时间。总解空间层为1到n+1。如下，3个元素，层数为1到4。

回溯法

2、解题思路

 /**
  * 回溯法搜索子集树的算法范式
  * output(x)     记录或输出得到的可行解x
  * constraint(t) 当前结点的约束函数
  * bount(t)      当前结点的限界函数
  * @param t 	  t为当前解空间的层数，从第0层开始。n为总解空间的层数
  */
void backtrace(int t)
{
    //这里可以有剪枝
    //....
    
    //一次搜索完成
	if (t > n)
	{
        //进行当前求最值、是否符合题意等情况的判断，符合则记录或输出！！！
		Output(x);
	}
	else
	{
        //相当于暴力枚举，列举全部情况
        //1、处理第t个个体，第t个个体有n种选择
		for (int i = 0; i <= n; i++)
		{
            //2、处理
			x[t] = i;
            //3、判断（最优性剪枝和可行性剪枝、是否已访问等）
            if (constrain(t) && bound(t))
            {
                backtrace(t + 1);
            }
            //4、恢复（简单的赋值后续可以重新覆盖，可以不进行恢复）
            ...
		}
	}	
}

3、例题

（1）0-1背包问题

两种以上选择，处理完要恢复。

回溯法

#include <stdio.h>

#define N 3         //物品的数量
#define C 16        //背包的容量

int w[4]={0,10,8,5};  //每个物品的重量
int v[4]={0,5,4,1};   //每个物品的价值
int x[4]={0,0,0,0};   //x[i]=1代表物品i放入背包，0代表不放入

int CurWeight = 0;  //当前放入背包的物品总重量
int CurValue = 0;   //当前放入背包的物品总价值

int BestValue = 0;  //最优值；当前的最大价值，初始化为0
int BestX[N];       //最优解；BestX[i]=1代表物品i放入背包，0代表不放入

void backtrack(int t)
{
    //一次搜索完毕
    if(t>N)
    {
        //如果找到了一个更优的解
        if(CurValue>BestValue)
        {
            //保存更优的值和解
            BestValue = CurValue;
            for(int i=1;i<=N;++i) BestX[i] = x[i];
        }
    }
    else
    {
        //遍历当前节点的子节点：0 不放入背包，1放入背包
        for(int i=0;i<=1;++i)
        {
            x[t]=i;

            if(i==0) //不放入背包
            {
                backtrack(t+1);
            }
            else //放入背包
            {
                 //约束条件：放的下
                if((CurWeight+w[t])<=C)
                {
                    CurWeight += w[t];
                    CurValue += v[t];
                    backtrack(t+1);
                    CurWeight -= w[t];	//恢复
                    CurValue -= v[t];
                }
            }
        }

    }
}

int main(int argc, char* argv[])
{
    backtrack(1);
    printf("最优值：%d\n",BestValue);
    for(int i=1;i<=N;i++)
    {
       printf("最优解：%-3d",BestX[i]);
    }
    return 0;
}

（2）N皇后问题

一个一个放。

第一个皇后放到第N个结束。充分利用问题隐藏的约束条件：每个皇后必然在不同的行(列)，每个行(列)必然也只有一个皇后。这样我们就**可以把第N个皇后放到第N个行中，使用Pos[i]表示皇后i在i行中的位置（也就是列号）（i = 0 to N-1）。**这样代码会大大的简洁，因为节点的子节点数目会减少，判断冲突也更简单。而且避免了重复的计算。

#include<bits/stdc++.h>
using namespace std;
int n;
int x[100];	//第t个放在第x[]列
int v[100]; //时间优化：标注第v[]列是否已被占用
int sum=0;

void output(){
    cout << "第" <<sum << "种放置方法为：" << endl;
 for(int i=1;i<=n;i++){
    cout << "(" <<i << "," << x[i] << ")" << endl;
 }

}
int place(int k){
   //遍历所有已经放的1到k-1个皇后位置
   for(int j=1;j<k;j++){
    if(x[j]==x[k] || abs(x[j]-x[k])== abs(j-k))	//不能同列，不能对角
        return 0;
   }
   return 1;
}
//递归
void backTrace(int t){
    if(t>n){ //摆完了，如果t>n说明已经放了n个，已经完成一次放置
        sum++;
        //output();
    }
    else{
        //处理第t个，有n种选择,尝试将第t个皇后放在第t行第x[t](i)列
        for(int i=1;i<=n;i++){
            //时间优化：第i列没有个体放置
            if(v[i] == 0){
               x[t]=i;
               if(place(t)){	//可以放在i位置处，则继续搜索
                    v[i] = 1;
                    BackTrace(t+1);
                    v[i] = 0;
               }
               //这里不可以省略！！
               x[t]=0; 
            }
        }

    }
}
//非递归
void backTrace1(){
   int k;
   x[1]=0;
   k=1;
   while(k>=1){
    x[k]+=1;////先放在第一个位置
    while((x[k]<=n && !(place(k)))){//如果不能放
        x[k]++;//  //放在下一个位置
    }
    if(x[k]<=n){
        if(k==n){// //如果已经放完了n个皇后
            sum++;
            //output();
        }
        else{//  //没有处理完，让k自加，处理下一个皇后
            k++;
            x[k]=0;
        }
    }else{// 当前无法完成放置，则进行剪枝，回溯回去，回到第k-1步
      k--;
    }
   }
}
int main()
{
    memset(x,0,sizeof(x));
    cin >> n;
    backTrace(1);
    //backTrace1();
    cout << sum;
    return 0;
}

（3）图的着色问题

https://www.cnblogs.com/ECJTUACM-873284962/p/8447050.html#_label3_1

（4）骑士游历问题

当情况比较复杂时，要学会自己处理：如使用数组等

https://www.cnblogs.com/cs-whut/p/11153529.html

（5）集合划分问题

https://www.cnblogs.com/ECJTUACM-873284962/p/8447050.html#_label3_1

（6）连续邮资问题？？？

**问题：**假设国家发行了k种不同面值的邮票，并且规定每张信封上最多只允许贴h张邮票。连续邮资问题要求对于给定的k和h的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。

思路：

（1）用stampval来保存各个面值，用maxval来保存当前所有面值能组成的最大连续面值。

（2）stampval[0] 一定等于1，因为1是最小的正整数。相应的，maxval[0]=1*h。

（3）stampval[0] 一定等于1，因为1是最小的正整数。相应的，maxval[0]=1*h。接下去就是确定第二个，第三个…第k个邮票的面值了。

（4）对于stampval[i+1]，它的取值范围是stampval[i]+1~maxval[i]+1。stampval[i]+1是因为这一次取的面值肯定要比上一次的面值大，而这次取的面值的上限是上次能达到的最大连续面值+1，是因为如果比这个更大的话，那么就会出现断层，即无法组成上次最大面值+1这个数了。

https://www.cnblogs.com/ECJTUACM-873284962/p/8447050.html#_label3_1

//标记每种取到的钱数 
//m使用了第m张邮票贴到邮件上进行凑总数，不能多于h张
void mark(int n,int m,int sum)
{  
    if(m>h) return;  
    vis[sum]=true;
    //现有n种数值不同的邮票可以凑数
    for(int i=1;i<=n;++i) mark(n,m+1,sum+stampval[i]);    
}

（7）符号三角形问题？

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kPQq2SYz-1595651301331)(C:\Users\ddjj6\AppData\Roaming\Typora\typora-user-images\1583325911845.png)]

**问题：**第一行有n个元素，对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。

思路：

（1）三角形所含符号总个数为n*(n+1)/2，当其为奇数时，显然不存在包含的"+“号个数与”-"号个数相同的符号三角形。此条件可用于剪枝。

（2）要会使用数组对三角形进行模拟。

（3）由题意知，只要第一行n个确定，整个三角型就确定了。

（4）第一行有n个符号，则此时三角形有n行。

#include<bits/stdc++.h>
using namespace std;
int n,half,counts,p[100][100],sum;//（2）

void backtrack(int t)
{
    if(t>n) sum++;
    else
    {
        for(int i=0;i<2;i++)
        {
            p[1][t]=i;//第一行符号
            counts+=i;//当前"+"号个数
            //由当前第一行符号情况得出整个三角形，遍历第二行到第t行   （3）（4）
            for(int j=2;j<=t;j++)
            {
                //条件
                p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];
                counts+=p[j][t-j+1];
            }
            if(!((counts>half)||(t*(t+1)/2-counts>half))){
                backtrack(t+1);
            }
            for(int j=2;j<=t;j++)
            {
                counts-=p[j][t-j+1];
            }
            counts-=i;
        }
    }
}

//第一行的符号个数,n*(n+1)/4,当前"+"号个数,符号三角矩阵,已找到的符号三角形数
int main()
{
    cin>>n;
    half=n*(n+1)/2;
    //（1）
    if(half%2==1)
    {
        cout<<"共有0个不同的符号三角形。"<<endl;
        return 0;
    }
    half=half/2;
    backtrack(1);
    cout<<"共有"<<sum<<"个不同的符号三角形。"<<endl;
}

https://www.cnblogs.com/ECJTUACM-873284962/p/8447050.html#_label3_1

（8）健康的荷斯坦奶牛？

字典序最小：注意这里从1往0开始枚举，因为题目希望字典序最小

import java.util.Scanner;
public class Main {
	
	static int v;
	static int[] need;
	static int g;
	static int[][] have;
	static int[] select;
	static int min = Integer.MAX_VALUE;
	static int[] best;
	static int flag = 0;
	public static void main(String[] args) {	
		Scanner in = new Scanner(System.in);
		v = in.nextInt();
		need = new int[v + 1];
		for(int i = 1;i <= v;i++) {
			need[i] = in.nextInt();
		}
		g = in.nextInt();
		select = new int[g + 1];
		best = new int[g + 1];
		for(int i = 1;i <= g;i++) {
			select[i] = 0;
			best[i] = 0;
		}
		have = new int[g + 1][v + 1]; 
		for(int i = 1;i <= g;i++) {
			for(int j = 1;j <= v;j++) {
				have[i][j] = in.nextInt();
			}
		}
		
		dfs(1,0);
		
		System.out.print(min + " ");
		for(int i = 1;i <= g;i++) {
			if(best[i] == 1) {
				System.out.print(i);
			}
			if(i < g && best[i] == 1) {
				System.out.print(" ");
			}
		}
		
	}
	
	public static void dfs(int t,int num) {
		if(num >= min) return;
		if(t > g) {
			if(judge(select)) {
				if(num < min) {
					min = num;
					for(int i = 1;i <= g;i++) {
						best[i] = select[i];
					}
				}
			}
		}else {
			//1、多种情况，注意这里从1往0开始枚举（因为题目希望字典序最小，故前面的要先考虑先选）
			for(int i = 1;i >= 0;i--) {
				//2、处理
				select[t] = i;
				//3、判断
				if(i == 0) {
					dfs(t + 1,num);
				}else if(i == 1) {
					dfs(t + 1,num + 1);
				}
				//4、回复
				select[t] = 0;
			}
		}
	
			
	}
	
	public static boolean judge(int[] select) {
		for(int j = 1;j <= v;j++) {
			int t = 0;
			for(int i = 1;i <= g;i++) {
				if(select[i] == 1) {
					t += have[i][j];
				}
			}
			if(t < need[j]) {
				return false;
			}
		}
		return true;
	}
	
	
}

（9）变换？？？？

https://www.luogu.com.cn/problem/P1037

import java.util.Scanner;
public class Main {
	
	static int[][] rule = new int[10][10];
	static int result = 0;
	static int num;
	public static void main(String[] args) {	
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = in.nextInt();
		for(int a = 0;a < k;a++) {
			int i = in.nextInt();
			int j = in.nextInt();
			rule[i][j] = 1;
		}
		num = get(n);
		
	}
	
	public static void dfs(int t) {
		if(t > num) {
			
		}else {
			
		}
			
	}
	
	public static boolean judge(int[] select) {
		for(int j = 1;j <= v;j++) {
			int t = 0;
			for(int i = 1;i <= g;i++) {
				if(select[i] == 1) {
					t += have[i][j];
				}
			}
			if(t < need[j]) {
				return false;
			}
		}
		return true;
	}
	
	public static int get(int n) {
		int o = 0;
		while(n != 0) {
			num++;
			n /= 10;
		}
		return o;
	}
	
}

（10）盾神与砝码称重？？

思路：

（1）每个砝码都可以选择放砝码盘、物品盘、不放（易错！）

（2）类似于0-1背包问题

https://www.dotcpp.com/oj/problem1548.html

回溯

import java.util.*;
 
public class Main
{

	static int m = 0,n = 0;
	static int[] fa = new int[25];
	static boolean flag = false;
	static int w;
	static int sum = 0;
    public static void main(String args[]) {
    	Scanner in = new Scanner(System.in);
    	n = in.nextInt();
    	m = in.nextInt();
    	for(int i = 1;i <= n;i++) {
    		fa[i] = in.nextInt();
    	}
    	for(int i = 0;i < m;i++) {
    		w = in.nextInt();
    		flag = false;
			dfs(1);
			if(flag) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
    	}
    }
    
    public static void dfs(int t) {
    	if(t > n) {
    		if(sum == w) {
    			flag = true;
    		}
    	}else {
    		for(int i = 0;i < 3;i++) {
    			if(i == 0) {
    				dfs(t + 1);
    			}
    			if(i == 1) {
    				sum += fa[t];
    				dfs(t + 1);
    				sum -= fa[t];
    			}
    			if(i == 2) {
    				sum -= fa[t];
    				dfs(t + 1);
    				sum += fa[t];
    			}
    		}
    	}
    	
    }

}

非回溯

import java.util.*;
 
public class Main
{

	static int m = 0,n = 0;
	static int[] fa = new int[25];
	static boolean flag = false;
	static int w;
    public static void main(String args[]) {
    	Scanner in = new Scanner(System.in);
    	n = in.nextInt();
    	m = in.nextInt();
    	for(int i = 1;i <= n;i++) {
    		fa[i] = in.nextInt();
    	}
    	for(int i = 0;i < m;i++) {
    		w = in.nextInt();
    		flag = false;
			dfs(0,1);
			if(flag) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
    	}
    }
    
    public static void dfs(int now,int index) {
    	if(now == w) {
    		flag = true;
    		return ;
    	}
    	if(index > n) {
    		return ;
    	}
    	dfs(now + fa[index],index + 1);
    	dfs(now - fa[index],index + 1);
    	dfs(now,index + 1);
    }

}

三、排序树问题

1、概念

当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。例如旅行售货员问题(如下图)的解空间树是一棵排列树，这类排列树通常有n!个叶结点。遍历子集树的算法需Ω(n!)计算时间。

根为第一层，n个数，n+1 层，从第一到第n个进行

特别适用于排序序列中

回溯法

2、解题思路

for if swap 处理递归恢复

/**
 * 
 * output(x)     树一次遍历结束，记录或输出得到的可行解x
 * constraint(t) 当前结点的题目约束函数
 * bount(t)      当前结点的数据限界函数
 * @param t      t为当前解空间的层数
 * @param n      n为条件给的个数
 */
   void backtrack(int t){
       if(t > n){
           //进行当前求最值、是否符合题意等情况的判断，符合则记录或输出！！！
       		output(x);
       }
       else{
            //第t层有（n-t+1）种交换方式
       		for (int i = t; i <= n; i++) {
                //1、（判断准备工作）先判断再交换（最后计算）
               //判断（最优性剪枝和可行性剪枝、是否已访问等）
               if(constraint(t) && bount(t)){
                    //交换
                   	swap(x[t], x[i]);
                    //（最后计算）
                    ...
                    backtrack(t+1);
               		swap(x[t], x[i]);
             	}
                //2、（判断准备工作）先交换再判断（最后计算）
                //swap(x[t], x[i]);  
                //if (constraint(t)&&bound(t)) backtrack(t+1);  
                //swap(x[t], x[i]); 
           }
       }
   }

backtrack（1）	//第一层开始从头到尾
backtrack（2）	//第一层固定（起点固定），从第二层开始

java swap()函数

	public static void swap(int i,int j) {
		int t = x[i];
		x[i] = x[j];
		x[j] = t;
	}

3、技巧

（1）注意初始化

初始化序列干脆为1 2 3 4 …… n

（2）求最优记录输出要判断

（3）推荐使用顺序：判断-交换-计算

（4）为什么要swap呢

这个swap其实是“挪”向了同层的其他节点，但这个地方我们没有建树，直接通过在这条路径上进行swap得到。

譬如，一条12345路径，我们从1出发1->2->3->4->5

那我们backtrace（2）的时候会把2和345交换位置，就是为了获得1->3,1->4,1->5开头的路径。

（5）一般数组下标都是从1开始，便于根据题意操作

（6）由backpack(t+1)知：若当前为第t层，则上一节点在第(t-1)层为x[t-1]，下一节点为x[i]

4、例题

（1）全排列问题

https://blog.csdn.net/long_long_int/article/details/79930888

非字典序：swap

#include<iostream>
using namespace std;
int n,a[100];
void dfs(int t)
{
	if(t>n)
	{
		for(int i=1;i<=n;i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<endl;
		return;
	}
	for(int i=t;i<=n;i++)
	{
		swap(a[i],a[t]);//交换 
		dfs(t+1);
		swap(a[i],a[t]);//回溯回来的时候一定要换回来 
	}
}
int main()
{
	while(cin>>n)
	{
		for(int i=1;i<=n;i++)
		{
			a[i]=i;//初始化a数组，第一次干脆定从小到大
		}
		dfs(1);
	}
}

字典序：子集树

#include<iostream>
using namespace std;
int n,a[100],v[100];
//a数组用于保存每一次的排列，v数组用于判断数字是不是已经被选过 
void dfs(int dp)//dp从1到n，执行n次，每次选择一个数 
{
	if(dp>n)//dp为n+1的时候，就说明已经选了n个，可以输出了； 
	{
		for(int i=1;i<=n;i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<endl;
		return;
	}
	for(int i=1;i<=n;i++) 
	{
        a[dp]=i;//保存当前选择 
		if(!v[i])//判断是不是选择过 
		{
			v[i]=1;//标记这个数字，防止同一个排列选择相同的数字。 
			dfs(dp+1);
			v[i]=0;//恢复
		}
	}
} 
int main()
{
	while(cin>>n)
	{
		dfs(1);
	}
}

（2）旅行商问题

起点已定，故从第2层开始即可

https://blog.csdn.net/lfb637/article/details/80635047

/**
   @回溯-旅行商(TSP)问题
*/
#include<iostream>
#include<algorithm>
#define MAX 100
using  namespace std;
int n;                               //城市个数
int a[MAX][MAX];                   //城市间距离
int x[MAX];                       //记录路径
int bestx[MAX]  = {0};           //记录最优路径
int bestp = 63355;              //最短路径长
int cp = 0;                    //当前路径长
void backpack(int t){
     if(t>n){
        //要能回去且距离仍最小
        if((a[x[n]][1])&&(a[x[n]][1]+cp<bestp)){
              bestp = a[x[n]][1]+cp;
              for(int i = 1;i<=n;i++){
                 bestx[i] = x[i];
              }
        }
     }else{
         for(int i = t;i<=n;i++){
             /*约束为当前节点到下一节点的长度不为0,限界为走过的长度+当前要走的长度之和小于最优长度
              *注意：backpack(t+1)当前为第t层，上一节点在第(t-1)层为x[t-1]，下一节点为x[i]
              */
             //1、判断（最优性剪枝和可行性剪枝）
             if((a[x[t-1]][x[i]])&&(cp+a[x[t-1]][x[i]]<bestp)){
                //2、交换
                swap(x[t],x[i]);   
                //3、计算
                cp+=a[x[t-1]][x[t]];
                backpack(t+1);
                //恢复
                cp-=a[x[t-1]][x[t]];
                swap(x[t],x[i]);
            }
        }
    }
}

int main(){
    cout<<"输入城市个数:"<<endl;
    cin>>n;      //顶点数
    //初始化序列
    for(int i = 1;i<=n;i++){
         x[i] = i;
    }
    cout<<"输入城市之间的距离(0表示城市间不通):"<<endl;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    //起点已定，故从第2层开始即可
    backpack(2);
    cout<<"最少旅行费用为: "<<bestp<<endl;
    cout<<"旅行路径为:"<<endl;
    for(int i = 1;i<=n;i++){
       cout<<bestx[i]<<" ";
    }
    cout<<bestx[1];
    return 0;
}
/*
4
0 30 6 4
30 0 5 10
6 5 0 20
4 10 20 0
*/

import java.util.Scanner;
public class Main {
	

	static int n;
	static int[][] a;
	static int[] x;
	static int now;
	static int[] r;
	static int min = Integer.MAX_VALUE;
	public static void main(String[] args) {	
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		a = new int[n + 1][n + 1];
		r = new int[n + 1];
		x = new int[n + 1];
		for(int i = 1;i <= n;i++) {
			x[i] = i;
		}
		for(int i = 1;i <= n;i++) {
			for(int j = 1;j <= n;j++) {
				a[i][j] = in.nextInt();
			}
		}
		dfs(2);
		System.out.println(min);
		for(int i = 1;i <= n;i++) {
			System.out.print(r[i]);
		}
		System.out.print(r[1]);
	}
	
	
	public static void dfs(int t) {
		if(t > n) {
			if(a[x[n]][x[1]] != 0 && now + a[x[n]][x[1]] < min) {
				min = now + a[x[n]][x[1]];
				for(int i = 1;i <= n;i++) {
					r[i] = x[i];
				}
			}
		}else {
			for(int i = t;i <= n;i++) {
				if(a[x[t - 1]][x[i]] != 0 && now + a[x[t - 1]][x[i]] < min) {
					now += a[x[t - 1]][x[i]];
					swap(i,t);
					dfs(t + 1);
					swap(i,t);
					now -= a[x[t - 1]][x[i]];
				}
			}
		}
	}
	
	public static void swap(int i,int j) {
		int t = x[i];
		x[i] = x[j];
		x[j] = t;
	}
	
}

（3）批处理作业调度问题

https://www.cnblogs.com/ECJTUACM-873284962/p/8447050.html#_label3_3

#include<iostream>
using namespace std;
#define MAX 200
int* x1;//作业Ji在机器1上的工作时间
int* x2;//作业Ji在机器2上的工作时间
int number=0;//作业的数目
int* xorder;//作业顺序
int* bestorder;//最优的作业顺序
int bestvalue=MAX;//最优的时间
int xvalue=0;//当前完成用的时间
int f1=0;//机器1完成的时间
int* f2;//机器2完成的时间


void backtrack(int t)
{
    if(t>number)
    {
        if(xvalue < bestvalue){
            for(int i=1;i<=number;i++) bestorder[i]=xorder[i];
                bestvalue=xvalue;
        }
    }
    else
    {
        for(int i=t;i<=number;i++)
        {
           //1、判断
           f1+=x1[xorder[i]];
           //计算该作业总时间
           f2[t]=(f2[t-1]>f1?f2[t-1]:f1)+x2[xorder[i]];
           //算入总时间
           xvalue+=f2[t];
           if(xvalue<bestvalue) {
                //2、交换
                swap(xorder[i],xorder[t]);
                backtrack(t+1);
                swap(xorder[i],xorder[t]);
           }
           //恢复
           xvalue-=f2[t];
           f1-=x1[xorder[i]];
       }
    }
}

int main()
{
    cout<<"请输入作业数目：";
    cin>>number;
    x1=new int[number+1];
    x2=new int[number+1];
    xorder=new int[number+1];
    bestorder=new int[number+1];
    f2=new int[number+1];
    x1[0]=0;
    x2[0]=0;
    xorder[0]=0;
    bestorder[0]=0;
    f2[0]=0;
    cout<<"请输入每个作业在机器1上所用的时间："<<endl;
    int i;
    for(i=1;i<=number;i++)
    {
        cout<<"第"<<i<<"个作业=";
        cin>>x1[i];
    }
    cout<<"请输入每个作业在机器2上所用的时间："<<endl;
    for(i=1;i<=number;i++)
    {
           cout<<"第"<<i<<"个作业=";
           cin>>x2[i];
    }
    for(i=1;i<=number;i++) xorder[i]=i;
    backtrack(1);
    cout<<"最节省的时间为："<<bestvalue<<endl;
    cout<<"对应的方案为：";
    for(i=1;i<=number;i++) cout<<bestorder[i]<<"  ";
    cout<<endl;
}

（4）圆排列问题？？？

https://www.cnblogs.com/ECJTUACM-873284962/p/8447050.html#_label3_6

代码中圆排列的圆心横坐标以第一个圆的圆心为原点。所以，总长度为第一个圆的半径+最后一个圆的半径+最后一个圆的横坐标。

#include<iostream>
#include<math.h>
using namespace std;
#define MAX 200

float minlen=10000,x[4],r[4];//当前最优值,当前圆排列圆心横坐标,当前圆排列
int n;//圆排列中圆的个数
//计算当前所选择圆的圆心横坐标
float center(int t)
{
    float temp=0;
    for(int j=1;j<t;j++)
    {
        //由x^2=sqrt((r1+r2)^2-(r1-r2)^2)推导而来
        float valuex=x[j]+2.0*sqrt(r[t]*r[j]);
        if(valuex>temp) temp=valuex;
    }
    return temp;
}
//计算当前圆排列的长度
void compute()
{
    float low=0,high=0;
    for(int i=1;i<=n;i++)
    {
        if(x[i]-r[i]<low) low=x[i]-r[i];
        if(x[i]+r[i]>high) high=x[i]+r[i];
    }
    if(high-low<minlen) minlen=high-low;
}
void backtrack(int t)
{
    if(t>n) compute();
    else
    {
        for(int j=t;j<=n;j++)
        {
            //为什么这样不可以？？把计算放在前面了！
            //float centerx=center(t);
            //if(centerx+r[t]+r[1]<minlen)
            //{
                //swap(r[t],r[j]);
                //x[t]=centerx;
                //backtrack(t+1);
                //swap(r[t],r[j]);
            //}
            //1、判断
            if(center(t)+r[t]+r[1]<minlen)
            {   //2、交换
                swap(r[t],r[j]);
                //3、计算
                x[t]=center(t);
                backtrack(t+1);
                swap(r[t],r[j]);
            }
        }
    }
}
int main()
{
    n=3;
    r[1]=1,r[2]=1,r[3]=2;
    cout<<"各圆的半径分别为："<<endl;
    for(int i=1;i<=3;i++) cout<<r[i]<<" ";
    cout<<endl;
    cout<<"最小圆排列长度为：";
    backtrack(1);
    cout<<minlen<<endl;
}

回溯法

一、概述

1、概念

2、注意

3、解题思路

4、技巧

二、子集树问题

1、概念

2、解题思路

3、例题

（1）0-1背包问题

（2）N皇后问题

（3）图的着色问题

（4）骑士游历问题

（5）集合划分问题

（6）连续邮资问题？？？

（7）符号三角形问题？

（8）健康的荷斯坦奶牛？

（9）变换？？？？

（10）盾神与砝码称重？？

三、排序树问题

1、概念

2、解题思路

3、技巧

4、例题

（1）全排列问题

（2）旅行商问题

（3）批处理作业调度问题

（4）圆排列问题？？？

python回溯法实现数组全排列输出实例分析

C#使用回溯法解决背包问题实例分析

PHP回溯法解决0-1背包问题实例分析

js回溯法计算最佳旅行线路代码实例

Python基于回溯法解决01背包问题实例

LeetCode 累加数（回溯法）

回溯法

回溯法

回溯法

回溯法