回溯法小总结+四个小例题(装载问题,01背包,n后,最大团,m着色)_...

建站1000 更新时间：2025-06-08 14:49:54

2023年8月1日发(作者：)

回溯法⼩总结+四个⼩例题（装载问题，01背包，n后，最⼤团，m着⾊）⽬录回溯法的基本策略回溯法的解空间回溯法基本思想回溯法解题步骤递归回溯和迭代回溯⼦集树和排列树装载问题01背包问题回溯法求解n后问题图的最⼤团问题图的m着⾊问题

回溯法的基本策略策略：回溯法在问题的解空间树中，按深度优先搜索，从根节点出发搜索解空间。算法搜索⾄某⼀结点时，先判断该结点是否包含问题的解，如果肯定不包含，则跳过，对以该节点为根的⼦树的搜索，逐层向其祖先回溯。否则，进⼊该⼦树，继续按照深度优先搜索。回溯法求解问题的所有解时，要回溯到根，且根节点的所有⼦树都已经搜索时遍历才结束。回溯法求解问题的⼀个解时，只要搜索到问题的⼀个解就可以结束。

回溯法的解空间⽤回溯法解决问题时，应明确问题的解空间。问题的解空间⾄少应包含问题的⼀个最优解。例如对于有3种可选物品的01背包问题，解空间包含所有的01取值可能如下：

(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1),总共8种可以选择的解。相应的解空间树如下

回溯法基本思想确定了解空间的组织结构之后，回溯从根节点以深度优先搜索开始，根节点⾸先成为⼀个活结点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深⽅向移⾄⼀个新节点。这个新节点就成为⼀个新的活结点，并成为当前扩展节点。如果当前扩展节点不能再向纵深⽅向移动，则当前的扩展节点就成为死结点。此时，往回回溯⾄最近的⼀个活节点处，并使这个活结点成为当前的扩展节点。

回溯法以这种⽅式递归地在解空间中搜索，直⾄找到所有要求的解或解空间已⽆活结点为⽌。

剪枝：在搜索⾄树中任⼀结点时，先判断该结点对应的部分解是否满⾜约束条件(约束函数)，或者是否超出⽬标函数的界(限界函数)；也即判断该结点是否包含问题的解，如果肯定不包含，则跳过对以该结点为根的⼦树的搜索，即剪枝；否则，进⼊以该结点为根的⼦树，继续按照深度优先的策略搜索。回溯法解题步骤回溯法步骤：针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先⽅式搜索解空间，并在搜索过程中利⽤剪枝函数(约束函数和限界函数)剪去⽆效的搜索。

递归回溯和迭代回溯回溯法具体使⽤的⼜可以使⽤递归回溯和迭代回溯：递归回溯：void BackTrack(int t){ if(t > n)Output(x); else { for(int i = f(n,t); i <= g(n,t); i++){ x[i] = h(i); if(Constraint(t) && Bound(t)) BackTrack(t+1); } }}注意⼏点 :上⾯的代码中，形式参数t表⽰递归深度，即当前扩展结点在解空间树中的深度。n控制递归深度，当t > n时，算法以及搜索到叶⼦结点，此时，由Output(x)记录或输出得到的可⾏解x。for循环中的f(n,t)和g(n,t)表⽰的是当前结点处未搜索过的⼦树的起始编号和终⽌编号。h(i)表⽰在当前结点处x[t] (t是层数)的第i个可选值。Constrain和Bound函数是约束函数和限界函数。执⾏完算法的for循环之后，已经搜索遍当前扩展结点的所有未搜索过的⼦树。BackTrack(t)已经执⾏完毕，返回t-1层继续执⾏，对还没有测试过的x[t-1]的值继续搜索。当t = 1时，若已经测试完x[1]的所有值，外层的调⽤就全部结束。⼀开始调⽤BackTrack(1)即可完成这次深度优先遍历。迭代回溯：//迭代回溯void IterativeBackTrack(){ int t = 1; //从第⼀层开始 while(t > 0){ if( f(n,t) <= g(n,t) ){ for(int i = f(n,t); i <= g(n,t); i++){//该层未搜索过的叶⼦的起始编号和终⽌编号 x[t] = h(i); if(Constraint(t) && Bound(t) ){ if(Solution(t)) Output(x); //已经达到叶⼦输出解 else t++; //下⼀层继续 } } } else t--; //回溯到上⼀层 }}注意⼀般回溯算法只保存从根节点到当前扩展结点的路径，如果解空间树中从根节点到叶⼦结点的最长路径的长度未h(n)，那么计算空间就是O(h(n))，如果需要显⽰的存储整个解，那么需要O(2^h(n))或者O(h(n!))内存空间。⼦集树和排列树两种解空间树：⼦集树：当所给的问题是从n个元素的集合S中找出满⾜某种性质的⼦集时，相应的解空间是⼦集树。例如01背包问题的解空间树就是⼦集树。这类树通常有2^n个叶⼦结点，结点总数是2^(n+1) - 1个。时间复杂度O(2^n)。排列树：当所给的问题是确定n个元素满⾜某种性质的排列的时候，相应的解空间树是排列树。排列树有n!个叶⼦结点，时间复杂度O(n!)。⽐较经典的有旅⾏售货员问题：售货员要去n个城市，已知各个城市之间的旅费，他要选定⼀条从驻地出发，经过每⼀个城市，最后回到驻地的路线使得总的消费最⼩。把这个问题组织成⼀颗排列树如下(1,2,3,4个城市)：⼦集树和排列树的代码如下：//⼦集树的⼀般算法void BackTrack(int t){ if(t > n)Output(x); else{ for(int i = 0; i <= 1; i++){ //只有左右⼦树两种可能 x[t] = i; if(Constraint(t) && Bound(t)) BackTrack(t+1); } }}//排列树的⼀般算法void BackTrack(int t){ if(t > n)Output(x); else { for(int i = t; i <= n; i++){ Swap(x[t],x[i]); if(Constraint(t) && Bound(t)) BackTrack(t+1); Swap(x[t],x[i]); } }}装载问题问题描述：就是将n个集装箱装⼊2艘载重量为C1,C2的轮船，其中集装箱i的重量为w[i]，问题要求如果可以装上去，求⼀个最优装载⽅案。

可以证明，先将第⼀个集装箱装满，剩余的装⼊第⼆个可以得到⼀个最优装载⽅案。然后使⽤回溯法设计装载问题。

普通的回溯法中如果不剪枝右⼦树的话，右⼦树可以直接进⼊，这样到达叶⼦结点的时候，要更新⼀下最优解，使⽤⼀个上界函数，⽤r表⽰剩余集装箱的重量，定义上界函数cw(当前的载重量)+r，如果cw+r <= bestw的话，就不⽤进⼊右⼦树。import edInputStream;import r;/** * 回溯法解决装载问题 * @author 郑鑫 */public class MaxLoading { private int n,C; private int cw,bestw,r;//当前载重量 private int[] w,x,bestx; public MaxLoading(int n, int c, int cw, int bestw, int r, int[] w, int[] x, int[] bestx) { super(); this.n = n; C = c; = cw; = bestw; this.r = r; this.w = w; this.x = x; = bestx; } public void BackTrack(int i){ if(i >= n){ if(cw > bestw){ for(int j = 1; j <= n; j++)bestx[j] = x[j]; bestw = cw; } return; } r -= w[i]; //剩下的重量 r ⼀开始赋值为所有w[i]的和 if(cw + w[i] <= C){ x[i] = 1; //装⼊ cw += w[i]; BackTrack(i+1); cw -= w[i]; x[i] = 0; } if(cw + r > bestw) { //只有⼤于才进⼊右⼦树 x[i] = 0; BackTrack(i+1); } r += w[i]; //回溯 } public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream()); int n = t(),r = 0; int C1 = t(); //第⼀艘轮船 int C2 = t(); //第⼆艘轮船 int[] w = new int [n+1]; int[] x = new int [n+1]; int[] bestx = new int [n+1]; for(int i = 1; i <= n; i++){ w[i] = t(); r += w[i]; } MaxLoading ml = new MaxLoading(n, C1, 0, 0, r, w, x, bestx); ack(1); int w1 = ; int w2 = 0; for(int i = 1; i <= n; i++)w2 += w[i]*(1-bestx[i]); if(w2 > C2){ n("---⽆法将全部物品装⼊两个集装箱!---"); }else { n("第⼀艘船装⼊的重量是 : " + w1); n("第⼆艘船装⼊的重量是 : " + w2); for(int i = 1; i <= n; i++){ if(bestx[i] == 1)n("物体" + i + "装⼊第⼀艘轮船!"); else n("物体" + i + "装⼊第⼆艘轮船!"); } } }}两个测试样例

01背包问题回溯法求解前⾯已经说过，01背包的解空间可以使⽤⼦集树表⽰。搜索解空间树时，只要其左⼉⼦结点是⼀个可⾏的结点(背包已经装的重量+w[i] <= C)，搜索就进⼊左⼦树。当右⼦树中有可能包含最优解时才进⼊右⼦树进⾏搜索，否则将右⼦树减去。试想，如果当前所剩的价值(Vleft)加上当前已经获得价值(nowV)⼩于等于记录好的最⼤价值(bestV)，右⼦树就没有必要搜索。剪枝函数更好的设计⽅法是：将剩余物品按照其单位重量价值降序排列。然后依此装⼊物品，直到装不下，再装⼀部分(实际上不可能(因为是01背包))，由此得到的价值是右⼦树中解的上界。举个栗⼦：n = 4,C = 7,v = [9,10,7,4],w = [3,5,2,1];

这四个物品的单位重量价值为[3,2,3.5,4]。按照递减的顺序装⼊物品，按照4,3,1物品序号装⼊后，背包容量仅剩1，这是我们再装0.2的物品2，此时，相应价值为22，解为[1,0.2,1,1]，尽管这不是可⾏解，但是可以知道其价值是最优值的上界。也就是说右⼦树按照这样装都⼩于当前的bestV的话就肯定剪枝。看代码吧：import edInputStream;import ist;import tions;import ator;import r;/*// *排序的另⼀种⽅法class UnitWSort implements Comparator{ //对单位重量的类按照单位重量d来排序 @Override

public int compare(UnitW o1,UnitW o2) { return -(() > () ? 1 :(() == () ? 0: -1));

}}*/class UnitW implements Comparable{ private double d; private int id; public UnitW(int id,double d) { super(); = id; this.d = d; } } public int getId() { return id; } public double getD() { return d; } @Override public int compareTo(UnitW o) { return -(this.d > o.d ? 1: (this.d == o.d ? 0: -1)); }}class Knapsack {

private int C; //背包容量 private int n; //物品数⽬ private int[] w; //物品重量 private int[] v; //物品价值 private int nowW; //当前重量 private int nowV; //当前价值 private int bestV; //当前最优价值 public int getBestV(){ //获得最优值 return bestV; } public Knapsack(int c, int n, int[] w, int[] v, int nowW, int nowV, int bestV) { super(); C = c; this.n = n; this.w = w; this.v = v; = nowW; = nowV; = bestV; } public void Backtrack(int i){ if(i >= n){ //达到叶⼦结点 bestV = nowV; return ; } if(nowW + w[i] <= C){ //能装就装,进⼊左边叶⼦ nowW += w[i]; nowV += v[i]; Backtrack(i+1); nowW -= w[i]; nowV -= v[i]; } if(Bound(i+1) > bestV){ //如果往右边⾛，背包装满了都没有现在的最优值，就剪枝这颗⼦树 Backtrack(i+1); } } //计算上界的函数 public double Bound(int i){ int Cleft = C - nowW; //剩余容量 int nowBest = nowV; while( i < n && w[i] < Cleft ){ //计算整数的 Cleft -= w[i]; nowBest += v[i]; i++; } //把背包装满 if(i < n)nowBest += v[i]*Cleft/w[i]; return nowBest;

} }}public class BackTrack01 { public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream()); int W = 0,V = 0,n,C; n = t(); C = t(); int[] w = new int[n+1];

int[] v = new int[n+1];

ArrayListunit = new ArrayList(); for(int i = 0; i < n; i++)w[i] = t();

for(int i = 0; i < n; i++)v[i] = t();

for(int i = 0; i < n; i++){ (new UnitW(i,v[i]*1.0/w[i]));

W += w[i]; V += v[i]; } if(W <= C){ n(V); (0); } (unit); //按照单位重量进⾏降序排序 //(unit,new UnitWSort()); //按照单位重量进⾏降序排序 //for(int i = 0; i < (); i++)n((i).getD()); int[] neww = new int[n+1];

int[] newv = new int[n+1]; for(int i = 0; i < n; i++){ neww[i] = w[(i).getId()]; newv[i] = v[(i).getId()];

} Knapsack K = new Knapsack(C,n,neww,newv,0,0,0); ack(0); //从第0层开始调⽤ n(tV()); }}效果

n后问题问题描述：n*n格的棋盘上放置彼此不受攻击的n个皇后，要求任何2个皇后不放在同⼀⾏或同⼀列或同⼀斜线上。

⽤n元组C[1:n]表⽰问题的解：C[i]表⽰的是i⾏皇后所在的列。

由于不允许两个皇后在同⼀列上，所以解向量中的C[i]互不相同。

还有⼀个要注意的就是2个皇后不能在同意斜线上，所以很容易得到两点之间的连线的斜率不能为1或-1，即：C[i] ! =C[col] &&abs(col-i) != abs(C[col] - C[i]);如图 import edInputStream;import r;public class NQueen { private int n; private int[] C; //i⾏C[i]列 -->代表的是解 private int sum; // 解的个数 private int[][] map; //输出解 //⼀开始都是0 public NQueen(int n,int sum,int[] C,int[][] map) { super(); this.n = n; = sum; this.C = C; = map; }

public int getSum(){ return sum; } public void BackTrack(int cur){ if(cur >= n){ sum++; for(int i = 0; i < n; i++)map[i][C[i]] = 1; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++)(map[i][j] + " "); n(); } n();

for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)map[i][j] = 0; } else for(int i = 0; i < n; i++){ //尝试在cur⾏的各列放置皇后 C[cur] = i; //cur⾏和i列 if(Constraint(cur))BackTrack(cur+1); //检查⼀下 -->可以的话就放置下⼀⾏ } } public boolean Constraint(int col){ for(int i = 0; i < col; i++){ if(C[i] == C[col] || ((col - i) == (C[col] - C[i])))return false; } return true; } public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream()); int n; n = t(); int[] C = new int[n+1]; int[][] map = new int[n+1][n+1]; for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)map[i][j] = 0; //赋初值0 int sum = 0; NQueen nq = new NQueen(n,sum,C,map); ack(0); n(()); }}展⽰⼀下8皇后的运⾏效果(只显⽰了两种解)

图的最⼤团问题最⼤团问题：

顺便看⼀下独⽴集，和最⼤团对应：

注意回溯的过程中：

设当前扩展结点Z位于解空间树的第i层：在进⼊左⼦树之前，必须确认从顶点i到以选⼊的顶点集中的每⼀个顶点有边相连。在进⼊右⼦树之前，必须确认还有⾜够多的可选择顶点使得算法有可能在右⼦树中找到更⼤的团，也就是说剩下的点加上⽬前的点要⽐保存的最多的点要⼤才搜索。import edInputStream;import r;/** * 最⼤团问题 * @author 郑鑫 */public class MaxClique { private int[][] map; //图的邻接矩阵 private int n; //图的顶点数 private int[] ans; //记录当前的解 private int[] ans; //记录当前的解 private int[] bestAns; //记录当前的最优解 private int nowN; //记录当前的顶点数 private int bestN; //记录最⼤的顶点数 public int getBestN(){ return bestN; } public void getBestAns(){ //输出最优解 for(int i = 0; i < n; i++)(bestAns[i] + " "); n(); n("----最⼤团中的点---"); for(int i = 0; i < n; i++)if(bestAns[i] == 1)(i+1 + " "); n(); } public MaxClique(int[][] map, int n, int[] ans, int[] bestAns, int nowN, int bestN) { super(); = map; this.n = n; = ans; s = bestAns; = nowN; = bestN; } public void BackTrack(int i){ if(i >= n){ for(int j = 0; j < i; j++)bestAns[j] = ans[j]; bestN = nowN; return; } boolean flag = true; for(int j = 0; j < i; j++){ if(map[i][j] == 0 && map[j][i] == 0&& ans[j] == 1){ //前⾯已经选的和这个不相连-->肯定不⾏(团的概念(完全图)) flag = false; break; } } if(flag){ //进⼊左⼦树

ans[i] = 1; nowN++; BackTrack(i+1); nowN--; //记得回溯的时候减掉 ans[i] = 0; //回溯

} if(nowN + n - i > bestN){ ans[i] = 0; //第i个不选 BackTrack(i+1); } } public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream()); int n,m; //顶点数，边数 n = t(); //顶点的序号是0~n-1 m = t(); int[] ans = new int[n+1] ;// 记录每⼀个顶点 for(int i = 0; i < n; i++) ans[i] = 0; //⼀开始都不在团⾥⾯

int[] bestAns = new int[n+1]; for(int i = 0; i < n; i++) bestAns[i] = 0; //⼀开始都不在团⾥⾯

int[][] map = new int[n+1][n+1]; for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)map[i][j] = 0; for(int i = 0; i < m; i++){ int a = t(); int b = t(); int b = t(); map[a-1][b-1] = map[b-1][a-1] = 1; } int bestN = 0; MaxClique mC = new MaxClique(map, n, ans, bestAns, 0, bestN); ack(0); n(tN()); tAns(); }}看这个例⼦和运⾏效果

图的m着⾊问题问题描述：

给定⽆向图G和m中不同的颜⾊，⽤这些颜⾊为图G的各个顶点着⾊，每个顶点着⼀种颜⾊。若⼀个图最少需要m中颜⾊才能使得图中每条边相连的2个顶点着不同的颜⾊。则称m为图的⾊数。

现在的问题是: 给你⼀个图G = (V,E)和m种颜⾊，如果这个图不是m可着⾊，给出否定答案，如果这个图是m可着⾊，找出所有的着⾊法。

例如下图四个顶点四条边，如果⽤三种(注意这题也可以⽤2种颜⾊，总的着⾊数是18，但是有三种颜⾊的着⾊法是12)颜⾊着⾊的12种情况

这个题⽬也是⽤⼀个ans数组保存解，ans[i] 表⽰的是顶点i ⽤的颜⾊是ans[i]，Ok函数的约束保证了相连的不是同⼀个颜⾊。 import edInputStream;import r;/** * 图的m着⾊问题 * @author 郑鑫 */public class Color { private int n; //图的顶点数 private int m; private int sum; private int[][] map; private int[] ans; //记录解 public int getSum(){ return sum; } public Color(int n, int m, int sum, int[][] map, int[] ans) { super(); this.n = n; this.m = m; = sum; = map; = ans; } public void BackTrack(int t){ if( t >= n){ sum++; //达到叶⼦结点，解的个数加1 for(int i = 0; i < t; i++)(ans[i] + " "); n(); return; }else for(int i = 0; i < m; i++){ ans[t] = i; if(Ok(t))BackTrack(t+1); } } //可⾏性约束 public boolean Ok(int i){ for(int j = 0; j < i; j++) if(map[i][j] == 1 && ans[j] == ans[i])return false; //如果相连⽽且颜⾊相同则不⾏ return true; } public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream()); int n = t(),edgeSum = t(),m = t(); //m是颜⾊数 int[] ans = new int[n+1]; for(int i = 0; i < n; i++)ans[i] = -1;

int[][] map = new int[n+1][n+1]; for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)map[i][j] = 0; for(int i = 0; i < edgeSum; i++){ int a = t(); int b = t(); map[a-1][b-1] = map[b-1][a-1] = 1; } Color c = new Color(n, m, 0, map, ans); ack(0); n(()); }}上⾯的例⼦输⼊：4 4 31 21 42 33 4上⾯的例⼦输出0 1 0 1

0 1 0 2

0 1 2 1

0 2 0 1

0 2 0 2

0 2 1 2

1 0 1 0

1 0 1 2

1 0 2 0

1 2 0 2

1 2 1 0

1 2 1 2

2 0 1 0

2 0 2 0

2 0 2 1

2 1 0 1

2 1 2 0

2 1 2 1

18

2023年8月1日发(作者：)

回溯法⼩总结+四个⼩例题（装载问题，01背包，n后，最⼤团，m着⾊）⽬录回溯法的基本策略回溯法的解空间回溯法基本思想回溯法解题步骤递归回溯和迭代回溯⼦集树和排列树装载问题01背包问题回溯法求解n后问题图的最⼤团问题图的m着⾊问题

回溯法的基本策略策略：回溯法在问题的解空间树中，按深度优先搜索，从根节点出发搜索解空间。算法搜索⾄某⼀结点时，先判断该结点是否包含问题的解，如果肯定不包含，则跳过，对以该节点为根的⼦树的搜索，逐层向其祖先回溯。否则，进⼊该⼦树，继续按照深度优先搜索。回溯法求解问题的所有解时，要回溯到根，且根节点的所有⼦树都已经搜索时遍历才结束。回溯法求解问题的⼀个解时，只要搜索到问题的⼀个解就可以结束。

回溯法的解空间⽤回溯法解决问题时，应明确问题的解空间。问题的解空间⾄少应包含问题的⼀个最优解。例如对于有3种可选物品的01背包问题，解空间包含所有的01取值可能如下：

(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1),总共8种可以选择的解。相应的解空间树如下

回溯法基本思想确定了解空间的组织结构之后，回溯从根节点以深度优先搜索开始，根节点⾸先成为⼀个活结点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深⽅向移⾄⼀个新节点。这个新节点就成为⼀个新的活结点，并成为当前扩展节点。如果当前扩展节点不能再向纵深⽅向移动，则当前的扩展节点就成为死结点。此时，往回回溯⾄最近的⼀个活节点处，并使这个活结点成为当前的扩展节点。

回溯法以这种⽅式递归地在解空间中搜索，直⾄找到所有要求的解或解空间已⽆活结点为⽌。

剪枝：在搜索⾄树中任⼀结点时，先判断该结点对应的部分解是否满⾜约束条件(约束函数)，或者是否超出⽬标函数的界(限界函数)；也即判断该结点是否包含问题的解，如果肯定不包含，则跳过对以该结点为根的⼦树的搜索，即剪枝；否则，进⼊以该结点为根的⼦树，继续按照深度优先的策略搜索。回溯法解题步骤回溯法步骤：针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先⽅式搜索解空间，并在搜索过程中利⽤剪枝函数(约束函数和限界函数)剪去⽆效的搜索。

递归回溯和迭代回溯回溯法具体使⽤的⼜可以使⽤递归回溯和迭代回溯：递归回溯：void BackTrack(int t){ if(t > n)Output(x); else { for(int i = f(n,t); i <= g(n,t); i++){ x[i] = h(i); if(Constraint(t) && Bound(t)) BackTrack(t+1); } }}注意⼏点 :上⾯的代码中，形式参数t表⽰递归深度，即当前扩展结点在解空间树中的深度。n控制递归深度，当t > n时，算法以及搜索到叶⼦结点，此时，由Output(x)记录或输出得到的可⾏解x。for循环中的f(n,t)和g(n,t)表⽰的是当前结点处未搜索过的⼦树的起始编号和终⽌编号。h(i)表⽰在当前结点处x[t] (t是层数)的第i个可选值。Constrain和Bound函数是约束函数和限界函数。执⾏完算法的for循环之后，已经搜索遍当前扩展结点的所有未搜索过的⼦树。BackTrack(t)已经执⾏完毕，返回t-1层继续执⾏，对还没有测试过的x[t-1]的值继续搜索。当t = 1时，若已经测试完x[1]的所有值，外层的调⽤就全部结束。⼀开始调⽤BackTrack(1)即可完成这次深度优先遍历。迭代回溯：//迭代回溯void IterativeBackTrack(){ int t = 1; //从第⼀层开始 while(t > 0){ if( f(n,t) <= g(n,t) ){ for(int i = f(n,t); i <= g(n,t); i++){//该层未搜索过的叶⼦的起始编号和终⽌编号 x[t] = h(i); if(Constraint(t) && Bound(t) ){ if(Solution(t)) Output(x); //已经达到叶⼦输出解 else t++; //下⼀层继续 } } } else t--; //回溯到上⼀层 }}注意⼀般回溯算法只保存从根节点到当前扩展结点的路径，如果解空间树中从根节点到叶⼦结点的最长路径的长度未h(n)，那么计算空间就是O(h(n))，如果需要显⽰的存储整个解，那么需要O(2^h(n))或者O(h(n!))内存空间。⼦集树和排列树两种解空间树：⼦集树：当所给的问题是从n个元素的集合S中找出满⾜某种性质的⼦集时，相应的解空间是⼦集树。例如01背包问题的解空间树就是⼦集树。这类树通常有2^n个叶⼦结点，结点总数是2^(n+1) - 1个。时间复杂度O(2^n)。排列树：当所给的问题是确定n个元素满⾜某种性质的排列的时候，相应的解空间树是排列树。排列树有n!个叶⼦结点，时间复杂度O(n!)。⽐较经典的有旅⾏售货员问题：售货员要去n个城市，已知各个城市之间的旅费，他要选定⼀条从驻地出发，经过每⼀个城市，最后回到驻地的路线使得总的消费最⼩。把这个问题组织成⼀颗排列树如下(1,2,3,4个城市)：⼦集树和排列树的代码如下：//⼦集树的⼀般算法void BackTrack(int t){ if(t > n)Output(x); else{ for(int i = 0; i <= 1; i++){ //只有左右⼦树两种可能 x[t] = i; if(Constraint(t) && Bound(t)) BackTrack(t+1); } }}//排列树的⼀般算法void BackTrack(int t){ if(t > n)Output(x); else { for(int i = t; i <= n; i++){ Swap(x[t],x[i]); if(Constraint(t) && Bound(t)) BackTrack(t+1); Swap(x[t],x[i]); } }}装载问题问题描述：就是将n个集装箱装⼊2艘载重量为C1,C2的轮船，其中集装箱i的重量为w[i]，问题要求如果可以装上去，求⼀个最优装载⽅案。

可以证明，先将第⼀个集装箱装满，剩余的装⼊第⼆个可以得到⼀个最优装载⽅案。然后使⽤回溯法设计装载问题。

普通的回溯法中如果不剪枝右⼦树的话，右⼦树可以直接进⼊，这样到达叶⼦结点的时候，要更新⼀下最优解，使⽤⼀个上界函数，⽤r表⽰剩余集装箱的重量，定义上界函数cw(当前的载重量)+r，如果cw+r <= bestw的话，就不⽤进⼊右⼦树。import edInputStream;import r;/** * 回溯法解决装载问题 * @author 郑鑫 */public class MaxLoading { private int n,C; private int cw,bestw,r;//当前载重量 private int[] w,x,bestx; public MaxLoading(int n, int c, int cw, int bestw, int r, int[] w, int[] x, int[] bestx) { super(); this.n = n; C = c; = cw; = bestw; this.r = r; this.w = w; this.x = x; = bestx; } public void BackTrack(int i){ if(i >= n){ if(cw > bestw){ for(int j = 1; j <= n; j++)bestx[j] = x[j]; bestw = cw; } return; } r -= w[i]; //剩下的重量 r ⼀开始赋值为所有w[i]的和 if(cw + w[i] <= C){ x[i] = 1; //装⼊ cw += w[i]; BackTrack(i+1); cw -= w[i]; x[i] = 0; } if(cw + r > bestw) { //只有⼤于才进⼊右⼦树 x[i] = 0; BackTrack(i+1); } r += w[i]; //回溯 } public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream()); int n = t(),r = 0; int C1 = t(); //第⼀艘轮船 int C2 = t(); //第⼆艘轮船 int[] w = new int [n+1]; int[] x = new int [n+1]; int[] bestx = new int [n+1]; for(int i = 1; i <= n; i++){ w[i] = t(); r += w[i]; } MaxLoading ml = new MaxLoading(n, C1, 0, 0, r, w, x, bestx); ack(1); int w1 = ; int w2 = 0; for(int i = 1; i <= n; i++)w2 += w[i]*(1-bestx[i]); if(w2 > C2){ n("---⽆法将全部物品装⼊两个集装箱!---"); }else { n("第⼀艘船装⼊的重量是 : " + w1); n("第⼆艘船装⼊的重量是 : " + w2); for(int i = 1; i <= n; i++){ if(bestx[i] == 1)n("物体" + i + "装⼊第⼀艘轮船!"); else n("物体" + i + "装⼊第⼆艘轮船!"); } } }}两个测试样例

01背包问题回溯法求解前⾯已经说过，01背包的解空间可以使⽤⼦集树表⽰。搜索解空间树时，只要其左⼉⼦结点是⼀个可⾏的结点(背包已经装的重量+w[i] <= C)，搜索就进⼊左⼦树。当右⼦树中有可能包含最优解时才进⼊右⼦树进⾏搜索，否则将右⼦树减去。试想，如果当前所剩的价值(Vleft)加上当前已经获得价值(nowV)⼩于等于记录好的最⼤价值(bestV)，右⼦树就没有必要搜索。剪枝函数更好的设计⽅法是：将剩余物品按照其单位重量价值降序排列。然后依此装⼊物品，直到装不下，再装⼀部分(实际上不可能(因为是01背包))，由此得到的价值是右⼦树中解的上界。举个栗⼦：n = 4,C = 7,v = [9,10,7,4],w = [3,5,2,1];

这四个物品的单位重量价值为[3,2,3.5,4]。按照递减的顺序装⼊物品，按照4,3,1物品序号装⼊后，背包容量仅剩1，这是我们再装0.2的物品2，此时，相应价值为22，解为[1,0.2,1,1]，尽管这不是可⾏解，但是可以知道其价值是最优值的上界。也就是说右⼦树按照这样装都⼩于当前的bestV的话就肯定剪枝。看代码吧：import edInputStream;import ist;import tions;import ator;import r;/*// *排序的另⼀种⽅法class UnitWSort implements Comparator{ //对单位重量的类按照单位重量d来排序 @Override

public int compare(UnitW o1,UnitW o2) { return -(() > () ? 1 :(() == () ? 0: -1));

}}*/class UnitW implements Comparable{ private double d; private int id; public UnitW(int id,double d) { super(); = id; this.d = d; } } public int getId() { return id; } public double getD() { return d; } @Override public int compareTo(UnitW o) { return -(this.d > o.d ? 1: (this.d == o.d ? 0: -1)); }}class Knapsack {

private int C; //背包容量 private int n; //物品数⽬ private int[] w; //物品重量 private int[] v; //物品价值 private int nowW; //当前重量 private int nowV; //当前价值 private int bestV; //当前最优价值 public int getBestV(){ //获得最优值 return bestV; } public Knapsack(int c, int n, int[] w, int[] v, int nowW, int nowV, int bestV) { super(); C = c; this.n = n; this.w = w; this.v = v; = nowW; = nowV; = bestV; } public void Backtrack(int i){ if(i >= n){ //达到叶⼦结点 bestV = nowV; return ; } if(nowW + w[i] <= C){ //能装就装,进⼊左边叶⼦ nowW += w[i]; nowV += v[i]; Backtrack(i+1); nowW -= w[i]; nowV -= v[i]; } if(Bound(i+1) > bestV){ //如果往右边⾛，背包装满了都没有现在的最优值，就剪枝这颗⼦树 Backtrack(i+1); } } //计算上界的函数 public double Bound(int i){ int Cleft = C - nowW; //剩余容量 int nowBest = nowV; while( i < n && w[i] < Cleft ){ //计算整数的 Cleft -= w[i]; nowBest += v[i]; i++; } //把背包装满 if(i < n)nowBest += v[i]*Cleft/w[i]; return nowBest;

} }}public class BackTrack01 { public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream()); int W = 0,V = 0,n,C; n = t(); C = t(); int[] w = new int[n+1];

int[] v = new int[n+1];

ArrayListunit = new ArrayList(); for(int i = 0; i < n; i++)w[i] = t();

for(int i = 0; i < n; i++)v[i] = t();

for(int i = 0; i < n; i++){ (new UnitW(i,v[i]*1.0/w[i]));

W += w[i]; V += v[i]; } if(W <= C){ n(V); (0); } (unit); //按照单位重量进⾏降序排序 //(unit,new UnitWSort()); //按照单位重量进⾏降序排序 //for(int i = 0; i < (); i++)n((i).getD()); int[] neww = new int[n+1];

int[] newv = new int[n+1]; for(int i = 0; i < n; i++){ neww[i] = w[(i).getId()]; newv[i] = v[(i).getId()];

} Knapsack K = new Knapsack(C,n,neww,newv,0,0,0); ack(0); //从第0层开始调⽤ n(tV()); }}效果

n后问题问题描述：n*n格的棋盘上放置彼此不受攻击的n个皇后，要求任何2个皇后不放在同⼀⾏或同⼀列或同⼀斜线上。

⽤n元组C[1:n]表⽰问题的解：C[i]表⽰的是i⾏皇后所在的列。

由于不允许两个皇后在同⼀列上，所以解向量中的C[i]互不相同。

还有⼀个要注意的就是2个皇后不能在同意斜线上，所以很容易得到两点之间的连线的斜率不能为1或-1，即：C[i] ! =C[col] &&abs(col-i) != abs(C[col] - C[i]);如图 import edInputStream;import r;public class NQueen { private int n; private int[] C; //i⾏C[i]列 -->代表的是解 private int sum; // 解的个数 private int[][] map; //输出解 //⼀开始都是0 public NQueen(int n,int sum,int[] C,int[][] map) { super(); this.n = n; = sum; this.C = C; = map; }

public int getSum(){ return sum; } public void BackTrack(int cur){ if(cur >= n){ sum++; for(int i = 0; i < n; i++)map[i][C[i]] = 1; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++)(map[i][j] + " "); n(); } n();

for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)map[i][j] = 0; } else for(int i = 0; i < n; i++){ //尝试在cur⾏的各列放置皇后 C[cur] = i; //cur⾏和i列 if(Constraint(cur))BackTrack(cur+1); //检查⼀下 -->可以的话就放置下⼀⾏ } } public boolean Constraint(int col){ for(int i = 0; i < col; i++){ if(C[i] == C[col] || ((col - i) == (C[col] - C[i])))return false; } return true; } public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream()); int n; n = t(); int[] C = new int[n+1]; int[][] map = new int[n+1][n+1]; for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)map[i][j] = 0; //赋初值0 int sum = 0; NQueen nq = new NQueen(n,sum,C,map); ack(0); n(()); }}展⽰⼀下8皇后的运⾏效果(只显⽰了两种解)

图的最⼤团问题最⼤团问题：

顺便看⼀下独⽴集，和最⼤团对应：

注意回溯的过程中：

设当前扩展结点Z位于解空间树的第i层：在进⼊左⼦树之前，必须确认从顶点i到以选⼊的顶点集中的每⼀个顶点有边相连。在进⼊右⼦树之前，必须确认还有⾜够多的可选择顶点使得算法有可能在右⼦树中找到更⼤的团，也就是说剩下的点加上⽬前的点要⽐保存的最多的点要⼤才搜索。import edInputStream;import r;/** * 最⼤团问题 * @author 郑鑫 */public class MaxClique { private int[][] map; //图的邻接矩阵 private int n; //图的顶点数 private int[] ans; //记录当前的解 private int[] ans; //记录当前的解 private int[] bestAns; //记录当前的最优解 private int nowN; //记录当前的顶点数 private int bestN; //记录最⼤的顶点数 public int getBestN(){ return bestN; } public void getBestAns(){ //输出最优解 for(int i = 0; i < n; i++)(bestAns[i] + " "); n(); n("----最⼤团中的点---"); for(int i = 0; i < n; i++)if(bestAns[i] == 1)(i+1 + " "); n(); } public MaxClique(int[][] map, int n, int[] ans, int[] bestAns, int nowN, int bestN) { super(); = map; this.n = n; = ans; s = bestAns; = nowN; = bestN; } public void BackTrack(int i){ if(i >= n){ for(int j = 0; j < i; j++)bestAns[j] = ans[j]; bestN = nowN; return; } boolean flag = true; for(int j = 0; j < i; j++){ if(map[i][j] == 0 && map[j][i] == 0&& ans[j] == 1){ //前⾯已经选的和这个不相连-->肯定不⾏(团的概念(完全图)) flag = false; break; } } if(flag){ //进⼊左⼦树

ans[i] = 1; nowN++; BackTrack(i+1); nowN--; //记得回溯的时候减掉 ans[i] = 0; //回溯

} if(nowN + n - i > bestN){ ans[i] = 0; //第i个不选 BackTrack(i+1); } } public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream()); int n,m; //顶点数，边数 n = t(); //顶点的序号是0~n-1 m = t(); int[] ans = new int[n+1] ;// 记录每⼀个顶点 for(int i = 0; i < n; i++) ans[i] = 0; //⼀开始都不在团⾥⾯

int[] bestAns = new int[n+1]; for(int i = 0; i < n; i++) bestAns[i] = 0; //⼀开始都不在团⾥⾯

int[][] map = new int[n+1][n+1]; for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)map[i][j] = 0; for(int i = 0; i < m; i++){ int a = t(); int b = t(); int b = t(); map[a-1][b-1] = map[b-1][a-1] = 1; } int bestN = 0; MaxClique mC = new MaxClique(map, n, ans, bestAns, 0, bestN); ack(0); n(tN()); tAns(); }}看这个例⼦和运⾏效果

图的m着⾊问题问题描述：

给定⽆向图G和m中不同的颜⾊，⽤这些颜⾊为图G的各个顶点着⾊，每个顶点着⼀种颜⾊。若⼀个图最少需要m中颜⾊才能使得图中每条边相连的2个顶点着不同的颜⾊。则称m为图的⾊数。

现在的问题是: 给你⼀个图G = (V,E)和m种颜⾊，如果这个图不是m可着⾊，给出否定答案，如果这个图是m可着⾊，找出所有的着⾊法。

例如下图四个顶点四条边，如果⽤三种(注意这题也可以⽤2种颜⾊，总的着⾊数是18，但是有三种颜⾊的着⾊法是12)颜⾊着⾊的12种情况

这个题⽬也是⽤⼀个ans数组保存解，ans[i] 表⽰的是顶点i ⽤的颜⾊是ans[i]，Ok函数的约束保证了相连的不是同⼀个颜⾊。 import edInputStream;import r;/** * 图的m着⾊问题 * @author 郑鑫 */public class Color { private int n; //图的顶点数 private int m; private int sum; private int[][] map; private int[] ans; //记录解 public int getSum(){ return sum; } public Color(int n, int m, int sum, int[][] map, int[] ans) { super(); this.n = n; this.m = m; = sum; = map; = ans; } public void BackTrack(int t){ if( t >= n){ sum++; //达到叶⼦结点，解的个数加1 for(int i = 0; i < t; i++)(ans[i] + " "); n(); return; }else for(int i = 0; i < m; i++){ ans[t] = i; if(Ok(t))BackTrack(t+1); } } //可⾏性约束 public boolean Ok(int i){ for(int j = 0; j < i; j++) if(map[i][j] == 1 && ans[j] == ans[i])return false; //如果相连⽽且颜⾊相同则不⾏ return true; } public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream()); int n = t(),edgeSum = t(),m = t(); //m是颜⾊数 int[] ans = new int[n+1]; for(int i = 0; i < n; i++)ans[i] = -1;

int[][] map = new int[n+1][n+1]; for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)map[i][j] = 0; for(int i = 0; i < edgeSum; i++){ int a = t(); int b = t(); map[a-1][b-1] = map[b-1][a-1] = 1; } Color c = new Color(n, m, 0, map, ans); ack(0); n(()); }}上⾯的例⼦输⼊：4 4 31 21 42 33 4上⾯的例⼦输出0 1 0 1

0 1 0 2

0 1 2 1

0 2 0 1

0 2 0 2

0 2 1 2

1 0 1 0

1 0 1 2

1 0 2 0

1 2 0 2

1 2 1 0

1 2 1 2

2 0 1 0