回溯法实验(最优装载)

一、实验目的1. 理解回溯法的概念和原理；2. 掌握回溯法的基本算法设计思想；3. 通过实例验证回溯法的正确性和效率；4. 深入了解回溯法在实际问题中的应用。

二、实验内容1. 实验一：八皇后问题2. 实验二：0/1背包问题3. 实验三：数独游戏三、实验原理回溯法是一种在解空间树中搜索问题解的方法。

其基本思想是：从问题的起始状态开始，通过尝试增加约束条件，逐步增加问题的解的候选集，当候选集为空时，表示当前路径无解，则回溯到上一个状态，尝试其他的约束条件。

通过这种方法，可以找到问题的所有解，或者找到最优解。

四、实验步骤与过程1. 实验一：八皇后问题（1）问题描述：在一个8x8的国际象棋棋盘上，放置8个皇后，使得任意两个皇后都不在同一行、同一列和同一斜线上。

（2）算法设计：- 定义一个数组，用于表示棋盘上皇后的位置；- 从第一行开始，尝试将皇后放置在第一行的每一列；- 检查当前放置的皇后是否与之前的皇后冲突；- 如果没有冲突，继续将皇后放置在下一行；- 如果冲突，回溯到上一行，尝试下一列；- 重复上述步骤，直到所有皇后都放置完毕。

（3）代码实现：```pythondef is_valid(board, row, col):for i in range(row):if board[i] == col or abs(board[i] - col) == abs(i - row):return Falsereturn Truedef solve_n_queens(board, row):if row == len(board):return Truefor col in range(len(board)):if is_valid(board, row, col):board[row] = colif solve_n_queens(board, row + 1):return Trueboard[row] = -1return Falsedef print_board(board):for row in board:print(' '.join(['Q' if col == row else '.' for col in range(len(board))]))board = [-1] 8if solve_n_queens(board, 0):print_board(board)2. 实验二：0/1背包问题（1）问题描述：给定一个背包容量为W，n件物品，每件物品的重量为w[i]，价值为v[i]，求在不超过背包容量的前提下，如何选取物品，使得总价值最大。

一、实验目的1. 理解回溯法的基本原理和适用场景。

2. 掌握回溯法在解决实际问题中的应用。

3. 通过实验，提高编程能力和算法设计能力。

二、实验背景回溯法是一种在计算机科学中广泛应用的算法设计方法。

它通过尝试所有可能的解，在满足约束条件的前提下，逐步排除不满足条件的解，从而找到问题的最优解。

回溯法适用于解决组合优化问题，如0-1背包问题、迷宫问题、图的着色问题等。

三、实验内容本次实验以0-1背包问题为例，采用回溯法进行求解。

1. 实验环境：Windows操作系统，Python 3.7以上版本。

2. 实验工具：Python编程语言。

3. 实验步骤：（1）定义背包容量和物品重量、价值列表。

（2）定义回溯法函数，用于遍历所有可能的解。

（3）在回溯法函数中，判断当前解是否满足背包容量约束。

（4）若满足约束，则计算当前解的价值，并更新最大价值。

（5）若不满足约束，则回溯至前一步，尝试下一个解。

（6）输出最优解及其价值。

四、实验结果与分析1. 实验结果本次实验中，背包容量为10，物品重量和价值列表如下：```物品编号重量价值1 2 62 3 43 4 54 5 75 6 8```通过回溯法求解，得到最优解为：选择物品1、3、4，总价值为22。

2. 实验分析（1）回溯法能够有效地解决0-1背包问题，通过遍历所有可能的解，找到最优解。

（2）实验结果表明，回溯法在解决组合优化问题时具有较高的效率。

（3）在实验过程中，需要合理设计回溯法函数，以提高算法的效率。

五、实验总结通过本次实验，我们了解了回溯法的基本原理和适用场景，掌握了回溯法在解决实际问题中的应用。

在实验过程中，我们提高了编程能力和算法设计能力，为今后解决类似问题奠定了基础。

在今后的学习和工作中，我们将继续深入研究回溯法及其应用，以期为解决实际问题提供更多思路和方法。

算法分析与设计实验报告学号姓名班级上课地点教师上课时间实验五回溯法1. 实验目的1.1掌握回溯法的设计思想；1.2 掌握解空间树的构造方法，以及在求解过程中如何存储求解路径；1.3 学会利用回溯法解决实际问题。

2. 实验环境2.1 Eclipse2.2 Window XP3. 实验内容3.1 旅行商问题：给定一个n顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。

输入：顶点个数、邻接矩阵；输出：最小耗费、旅行的环路。

3.2 n后问题：nXn棋盘上放置n个皇后使得每个皇后互不受攻击，即任二皇后不能位于同行同列和同一斜线上。

输入：皇后的个数，输出：所有可能的方案以及总的方案数。

4. 教师批改意见成绩签字：日期：实验报告细表1旅行商问题1.1 算法设计思想回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。

这个开始结点就成为一个活结点，同时也成为当前的扩展结点。

在当前的扩展结点处，搜索向纵深方向移至一个新结点。

这个新结点就成为一个新的活结点，并成为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。

此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。

回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

1.2 程序源码package lvxingshang;import java.util.Scanner;public class Bttsp {static int n; // 图G的顶点数static int[] x; // 当前解static int[] bestx; // 当前最优解static float bestc; // 当前最优值static float cc; // 当前费用static float[][] a; // 图G的邻接矩阵public static void tsp() {// 置x为单位矩阵x = new int[n + 1];for (int i = 1; i <= n; i++) {x[i] = i;}bestc = (float) -1.0;bestx = new int[n + 1];cc = 0;System.out.println("最短路线为：");backtrack(2);for (int i = 1; i <= n; i++) {System.out.print(bestx[i] + " ");}System.out.println("1");}private static void backtrack(int i) {if (i == n) {if (a[x[n - 1]][x[n]] > 0&& a[x[n]][1] > 0&& (bestc < 0 || cc + a[x[n - 1]][x[n]]+ a[x[n]][1] < bestc)) {for (int j = 1; j <= n; j++) {bestx[j] = x[j];bestc = cc + a[x[n - 1]][x[n]] + a[x[n]][1];}}}else{for (int j = i; j <= n; j++)// 是否可以进入x【j】子树？if (a[x[i - 1]][x[j]] > 0&& (bestc < 0 || cc + a[x[i - 1]][x[j]] < bestc)) { // 搜索子树int temp = x[i];cc += a[x[i - 1]][x[j]];x[i] = x[j];x[j] = temp;backtrack(i + 1);temp = x[i];x[i] = x[j];x[j] = temp;cc -= a[x[i - 1]][x[j]];}}}public static void main(String[] args) {Scanner s = new Scanner(System.in);System.out.println("请输入售货员要去的城市个数：");String line = s.nextLine();// 读入nn = Integer.parseInt(line);a = new float[n + 1][n + 1];System.out.println("请输入来往各个城市之间的花费 \n");for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {a[i][j] = s.nextFloat();}}tsp();System.out.println("最短距离是：" + bestc);s.close();}}1.3 实验结论1.4 心得体会由于编程途中最优解一直输不出，尝试着各种方法，觉得很累。

装载问题（回溯法）1、问题有n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且∑wi <= c1 + c2。

问是否有⼀个合理的装载⽅案,可将这n个集装箱装上这2艘轮船。

如果有，找出⼀种装载⽅案。

2、解析c1和c2是相互独⽴的，即如何在c1或者c2上，放置物品是互不⼲扰的。

但是假如先在c1上放置货物，则因剩下的货物不同，会使c2上装载的货物的情况发⽣变化。

因此，为了保证c1上装载的情况，满⾜c1和c2将所有的货物都装下，c1上应该尽可能的多放物品。

3、设计1 #include<bits/stdc++.h>2using namespace std;3const int num=100;4int n,c1,c2,w[num];// n个集装箱，A,B货轮载重量分别为C1，C2，W[i],第i个集装箱的重量5int cw,bw,rw;//cw，当前集装箱货物重量；bw，最优载重重量，rw，剩余集装箱重量；6int x[num],bx[num];//x[]，A货轮的当前结果；bx[]，A货轮的最优结果；7void BackTrack(int i) {8//处理完了前n个集装箱；9if(i>n){10if(cw>bw){//cw，⽬前A中装了cw重量的集装箱；11//更新最优解；12 bw=cw;13for(int i=1;i<=n;i++) bx[i]=x[i];14 }15return;16 }17//rw表⽰处理完第i个之后（选或不选），还剩下rw-w[i]重量的集装箱未处理；18 rw-=w[i];19if(cw+w[i]<=c1){//cw，第i个货箱之前的重量 + 第i个货箱⼩于A的最⼤重量C1；20 cw+=w[i];//加上21 x[i]=1;//标记i被选22 BackTrack(i+1);23 cw-=w[i];//减去重量24 x[i]=0;//撤销标记；25 }26//不选择第i个物品的话；27//if cw：表⽰[1:i)的数据 rw:表⽰(i,n]的数据，不包括第i个的数据28//如果不包括第i的数据的和（cw+rw）⼤于⽬前最优解bw，则可以递归下去；29if(cw+rw > bw){30 x[i]=0;31 BackTrack(i+1);32 }3334//处理完第i个物品当前的情况了；35//因为再上⼀层，有两种情况；36//1；选择第i物品；37//2：不选择第i个物品38//如果⽬前处理的是上⼀层第1种情况，那么我们就有必要加上这个w[i];39//否则会影响上⼀层处理第2种情况；40 rw+=w[i];41return ;42}43int main(){44 scanf("%d%d%d",&n,&c1,&c2);45for(int i=1;i<=n;i++) {46 scanf("%d",&w[i]);47 rw+=w[i];//rw表⽰⽬前最优集装箱的剩余重量；48 }49//递归回溯50 BackTrack(1);51//bw表⽰A货轮装下的货物重量；剩余的重量 > B可以放下的最多，则不可；52if(rw-bw>c2){53 printf("没有装载⽅案\n");54 }else{55 printf("货轮A：\n");56for(int i=1;i<=n;i++) {57if(bx[i]) {58 printf("%d ",i);59 }60 }61 printf("\n货轮B：\n");62for(int i=1;i<=n;i++) {63if(0==bx[i]) {64 printf("%d ",i);65 }66 }67 }68return0;69 }4、分析最坏情况要遍历图中所有结点，算法的时间复杂度为O(2")。

最优装载问题（贪⼼）⼀、实验内容运⽤贪⼼算法解决活动安排问题（或最优装载问题）使⽤贪⼼算法解决最优装载问题。

⼆、所⽤算法基本思想及复杂度分析1.算法基本思想贪⼼算法是指在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。

⽤局部解构造全局解，即从问题的某⼀个初始解逐步逼近给定的⽬标，以尽可能快的求得更好的解。

当某个算法中的某⼀步不能再继续前进时，算法停⽌。

2.问题分析及算法设计问题分析：（1）给定n个古董，要把它们装到装载量为c的装载船上。

（2）⾸先需要对这n个古董进⾏质量从⼩到⼤的排序。

（3）然后每次都选择最轻的，接着再从剩下的n-1件物品中选择最轻的。

（4）重复第（3）步骤，直到当前载重量⼤于装载船的最⼤装载量，停⽌装载。

（5）此时得到最优的贪⼼⽅案，记录下装载的最⼤古董数。

算法设计：（1）算法策略：把n件物品从⼩到⼤排序，然后根据贪⼼策略尽可能多的选出前i个物品，直到不能装为⽌。

（2）特例：算法复杂度分析由最优装载问题的贪⼼选择性质和最优⼦结构性质，可知将这些古董按照其重量从⼩到⼤排序，所以算法所需的计算时间为O（nlogn）。

三、源程序核⼼代码及注释（截图）四、运⾏结果五、调试和运⾏程序过程中产⽣的问题及解决⽅法，实验总结（5⾏以上）这⾥的调试，没有什么⼤问题，单纯的依次⽐较，判断，从⽽得到结果。

这次实验让我对贪⼼算法有了更深刻的认识，其主要是从问题的初始解出发，按照当前最佳的选择，把问题归纳为更⼩的相似的⼦问题，并使⼦问题最优，再由⼦问题来推导出全局最优解。

贪⼼算法虽然求的是局部最优解，但往往许多问题的整体最优解都是通过⼀系列的局部最优解的选择来达到的，所以贪⼼算法不⼀定可以得到能推导出问题的最优解，但其解法是最优解的近似解。

懂得算法的原理，还需要多去练习才能更好的掌握其⽤法。

源码：#include<iostream>#include<algorithm>#define MAXN 1000005using namespace std;int w[MAXN];//每件古董的重量int main(){int c,n;//c:载重量，n古董数int sum = 0;//装⼊古董的数量int tmp = 0;//装⼊古董的重量cin >> c >> n;for(int i= 1; i <= n; ++i)cin >> w[i];sort(w+1,w+1+n);for(int i = 1; i <= n; ++i){tmp += w[i];if(tmp <= c)++sum;elsebreak;}cout << sum << endl;return 0;}。

实验六 回溯算法〔2学时〕一、实验目的与要求1、掌握装载问题的回溯算法；2、初步掌握回溯算法；二、实验题有一批共n 个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i 的重量为wi ，且 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。

如果有，找出一种装载方案。

三、实验提示void backtrack (int i){// 搜索第i 层结点if (i > n) // 到达叶结点更新最优解bestx,bestw;return;r -= w[i];if (cw + w[i] <= c) {// 搜索左子树x[i] = 1;cw += w[i];backtrack (i + 1);cw -= w[i]; }if (cw + r > bestw) {x[i] = 0; // 搜索右子树backtrack (i + 1); }r += w[i];}四、实验代码方法1：import java.util.*;/*** 回溯法解决装载问题* author Administrator**/public class demo {public static int n; //集装箱数public static int first_weight; //第一艘载重量public static int beautif_weight; //当前最优载重量public static int[] arr_weight; //集装箱重量数组public static int[] **; //public static int[] best**;public static int maxLoadingRE(int[] w, int c, int[] bestx) {//递归回溯 n = w.length;first_weight = c;beautif_weight = 0;211c c w n i i +≤∑=arr_weight = w;best** = bestx;** = new int[n];int r = 0; //剩余集装箱重量，未进展装载的重量for (int i = 0; i < n; i++) {r += arr_weight[i];}trackback(0, 0, r);return beautif_weight;}//到达层数，目前装载的重量，未装载的重量private static void trackback(int i, int cw, int r) {if (i == n) {//到达叶结点for (int j = 0; j < n; j++) {best**[j] = **[j];}beautif_weight = cw;return; //只是一次出栈操作，栈非空还要继续执行}if (cw + arr_weight[i] <= first_weight) { //已装载的加上要装载的小于第一个的载重量**[i] = 0; //0代表装在第一个上，1代表装在第二个上trackback(i + 1, cw + arr_weight[i], r); //试图装载下一个集装箱，r是针对第一个装的重量，因此装在第一个里不需要减，但装在第二个时就要减去该重量}if (r - arr_weight[i] > beautif_weight) { //已装载的加上要装载的已经大于第一个的载重量，并且用总的载重量r减去当前要装载的还比最好的载重量大**[i] = 1; //放到第二个上trackback(i + 1, cw, r - arr_weight[i]);}}public static int maxLoading(int[] w, int c, int[] bestx) {int i = 0; //当前层int n = w.length; //层总数int[] x = new int[n]; //x[0, i]为当前选择路径Arrays.fill(x, -1); //初始化为-1，0表示选择第一个，1表示选择第二个int bestw = 0; //当前最优装载重量int[] cw = new int[n]; //当前载重量int[] r = new int[n]; //剩余集装箱容量int tor = 0;for (int item : w) {//item取出w中的值，进展相加tor += item;}r[0] = tor;//要装载的重量cw[0] = 0;//搜索子树while (i > -1) {do {x[i] += 1;if (x[i] == 0) { //选择放在第一个〔左子树〕if (cw[i] + w[i] <= c) {if (i < n - 1) {cw[i + 1] = cw[i] + w[i];r[i + 1] = r[i];}break; //能放下就直接跳出这个do-while循环}}else { //选择放在第二个〔右子树〕if (r[i] - w[i] > bestw) {//剪枝函数，没有最优解好的话x[i]会自增到2，不会进入下面的if (x[i] < 2)if (i < n - 1) {r[i + 1] = r[i] - w[i];cw[i + 1] = cw[i];}break;}}} while (x[i] < 2); //对于放不下的在这里判断后才能取右子树if (x[i] < 2) {if (i == n - 1) {for (int j = 0; j < n; j++) {bestx[j] = x[j];}if (x[i] == 0) {bestw = cw[i] + w[i];}else {bestw = cw[i];}}else {i++;x[i] = -1;}}else {//当x[i]=2时，说明已经遍历完两个叶节点，应向上一层继续遍历其它节点i--;}}return bestw;}public static void main(String[] args) {int[] w = {0,10,40,40};int n = w.length;int c = 50;int[] bestx = new int[n];System.out.println("重量分别为：");for(int ws:w){System.out.print(","+ws);}System.out.println("\n");int bestw = maxLoadingRE(w, c, bestx);System.out.println("回溯选择结果为: " + bestw); System.out.println(Arrays.toString(bestx));}}方法2：public class demo2 {public static void main(String[] args) {int n=3,m;int c=50,c2=50;int w[]={0,10,40,40};int bestx[]=new int[w.length];demo2 demo2=new demo2();m=demo2.MaxLoading(w, c, n, bestx);System.out.println("轮船的载重量分别为：");System.out.println("c(1)="+c+",c(2)="+c2);System.out.println("待装集装箱重量分别为：");System.out.print("w(i)=");for (int i=0;i<=n;i++){System.out.print("，"+w[i]);}System.out.println(");System.out.println("最优装载量为：");System.out.println("m(1)="+m);System.out.print("x(i)=");for (int i=0;i<=n;i++){System.out.print("+bestx[i]);}System.out.println(");int m2=0;for (int j=1;j<=n;j++){m2=m2+w[j]*(1-bestx[j]);}System.out.println("回溯选择结果为:"+m2);if(m2>c2){System.out.println("因为m(2)大于c(2),所以原问题无解！");}}int MaxLoading(int w[],int c,int n,int bestx[])//迭代回溯法，返回最优载重量及其相应解，初始化根结点{int i=1;//当前层，x[1:i-1]为当前路径int x[]=new int[n+1];int bestw=0; //当前最优载重量int cw=0; //当前载重量int r=0; //剩余集装箱重量for (int j=1;j<=n;j++){r+=w[j];}while(true)//搜索子树{while(i<=n &&cw+w[i]<=c)//进入左子树{r-=w[i];cw+=w[i];x[i]=1;i++;}if (i>n)//到达叶结点{for (int j=1;j<=n;j++){bestx[j]=x[j];}bestw=cw;}else//进入右子树{r-=w[i];x[i]=0; i++;}while (cw+r<=bestw){ //剪枝回溯i--;while (i>0){r+=w[i];i--;}//从右子树返回if (i==0){return bestw;}x[i]=0;cw-=w[i];i++;}}}}五、实验结果六、实验总结。

回溯法实验（0-1 背包问题）算法分析与设计实验报告第丄次附加实验巔I 軌鬻123^EC70?1O牧品价值分别为：12345678? 10妆品重量和忙值分别为；<2^2> <3,3> <4.4>O^SJ C9,9) <18,10>在实验中并没有生成多组数据，进行比较，也没有利用随机生 成函数，因为在这种有实际有关联的问题中，利用随机生成函数生 成的数据是十分的不合适的，在此我们只需要验证该程序是否正确 即可。

0-1背包问题和之前的最优装载其实质上一样的，都是利用 解空间树，通过深度优先搜索子集树，通过利用上界函数和一些剪 枝策略，从而得到最优解。

由于数据较小，所以时间上并不能反映 出什么东西。

当输入的数据有解时:测试结果实验分析当输入的数据无解时:当输入的数据稍微大点时:四回溯法X FUFO ORe\Debuq\zeno cnejext阀品上数为：M在这一章的回溯算法中，我们用的比较多的就是；利用子集树 来进行问题的探索，就例如上图是典型的一种子集树，在最优装 载、0-1背包都是利用了这种满二叉树的子集树进行求解，然后通 过深度优先的策略，利用约束函数和上界函数，将一些不符合条件 或者不包含最优解的分支减掉，从而提高程序的效率。

对于0-1背包问题我们基本上在每一个算法中都有这么一个实例，足以说明这 个问题是多么经典的一个问题啊，通过几个不同的算法求解这一问 题，我也总算对该问题有了一定的了解。

实验得分附录：完整代码(回溯法)〃0-1背包问题 回溯法求解#i nclude <iostream> using namespacestd;template <class Typew, class Typep> class Knap //Knap 类记录解空间树的结点信息{template <class Typew, class Typep>friend Typep Knapsack(Typep [],Typew [],Typew, int );private :Typep Bound( int i);//计算上界的函数实验心得 助教签名void Backtrack( int i); //回溯求最优解函数Typew c; //背包容量int n; //物品数Typew *w; //物品重量数组|Typep *p; //物品价值数组Typew cw; //当前重量Typep cp; //当前价值Typep bestp; //当前最后价值};template <class Typew, class Typep>Typep Knapsack(Typep p[],Typew w[],Typew c, int n); //声明背包问题求解函数template < class Type>in li ne void Swap (Type &a,Type & b); // 声明交换函数template <class Type>void BubbleSort(Type a[], int n); // 声明冒泡排序函数int main(){int n ; //物品数int c ; //背包容量cout«"物品个数为：";cin»n;cout«"背包容量为：";cin> >c;int *p = new int [n]; //物品价值下标从1开始int *w = new int [n]; //物品重量下标从1开始cout«"物品重量分别为："<<e ndl;for (int i=1; i<=n; i++){cin> >w[i];}cout«"物品价值分别为："<<e ndl;for (int i=1; i<=n; i++) //以二元组(重量，价值)的形式输出每物品的信息{cin> >p[i];}coutvv "物品重量和价值分别为："<<e ndl;for (int i=1; i<=n; i++) //以二元组(重量，价值)的形式输出每个物品的信息{coutvv "(" <<w[i]<< "," <<p[i]<< ")";}coutvve ndl;coutvv "背包能装下的最大价值为："<<Knapsack(p,w,c,n)<<endl; //输出结果system( "pause");return 0;}template vclass Typew, class Typep>void Knap<Typew,Typep>::Backtrack( int i){if (i>n) //到达叶子节点{bestp = cp; //更新最优值return ;}if (cw + w[i] <= c) // 进入左子树{cw += w[i];cp += p[i]；Backtrack(i+1); // 回溯//回溯结束回到当前根结点cw -= w[i];cp -= p[i]；}//进入右子树，条件是上界值比当前最优值大，否则就将右子树剪掉if (Bound(i+1)>bestp){Backtrack(i+1);}}template <class Typew, class Typep>Typep KnapvTypew, Typep>::Bound( int i) //计算上界{Typew cleft = c - cw; // 剩余容量Typep b = cp;//以物品单位重量价值递减序装入物品while (i <= n && w[i] <= cleft){cleft -= w[i];b += p[i];i++;}//如果背包剩余容量不足以装下一个物品if (i <= n){b += p[i]/w[i] * cleft; //则将物品的部分装入到背包中}return b;}class Object //定义对象类，作用相当于结构体{template vclass Typew, class Typep>friend Typep Knapsack(Typep[],Typew [],Typew, int ); public : int operator >= (Object a) const // 符号重载函数，重载>=符号{return (d>=a.d);}private :int ID; // 编号float d; //单位重量的价值};template <class Typew, class Typep>Typep Knapsack(Typep p[],Typew w[],Typew c, int n){// 为Knap::Backtrack 初始化Typew W = 0;Typep P = 0;Object *Q = newObject[n]; // 创建Object 类的对象数组| //初始化Object类的对象数组|for (int i=1; i<=n; i++){Q[i-1] .ID = i;Q[i-1].d = 1.0 * p[i]/w[i];P += p[i];W += w[i];}if (W <= c) //装入所有物品{return P;}//依物品单位重量价值降序排序BubbleSort(Q, n);Knap<Typew,Typep> K; // 创建Knap的对象KK.p = n ewTypep[ n+1];K.w = n ewTypew [n+1];for (int i=1; i<=n; i++){K.p[i] = p[Q[i-1]」D];K.w[i] = w[Q[i-1].ID];}//初始化KK.cp = 0;K.cw = 0;K.c = c;K.n = n;K.bestp = 0;//回溯搜索K.Backtrack(1);delete []Q;delete []K.w;delete []K.p;return K.bestp; // 返回最优解} template <class Type>void BubbleSort(Type a[], int n) {//记录一次遍历中是否有元素的交换bool excha nge;for (int i=0; i<n-1;i++){exchange = false ;for (int j=i+1; j<=n-1; j++){if (a[j]>=a[j-1]){Swap(a[j],a[j-1]); exchange = true ;}}//如果这次遍历没有元素的交换，那么排序结束if (exchange==false ){break ;}}} template < class Type>inline void Swap (Type &a,Type &b) // 交换函数{Type temp = a; a = b;b = temp;}。

装载问题-回溯法问题描述： 有⼀批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量是wi，且不能超。

算法思想： 最优装载⽅案：将第⼀艘轮船尽可能的装满； 然后将剩余的装载第⼆艘船上算法描述：template <class Type>class Loading{friend Type MaxLoading(Type [],Type,int);private:void Backtrack(int i);int n;Type * w,c,cw,bestw;};template <class Type>void Loading<Type>::Backtrack(int i){if(i>n){if(cw>bestw)bestw = cw;return;}if(cw+w[i] <= c){cw += w[i];Backtrack(i+1);cw -= w[i];}Backtrack(i+1);}template <class Type>Type MaxLoading(Type w[],Type c,int n){Loading<Type> X;X.w = w;X.c = c;X.n = n;X.bestw = 0;X.cw = 0;X.Backtrack(1);return X.bestw;}上界函数：引⼊上界函数，⽤于剪去不含最优解的⼦树：template <class Type>class Loading{friend Type MaxLoading(Type [],Type,int);private:void Backtrack(int i);int n;Type * w,c,cw,bestw,r;//剩余集装箱重量};template <class Type>void Loading<Type>::Backtrack(int i){if(i>n){if(cw>bestw)bestw = cw;return;}r-=w[i];//计算剩余的集装箱的重量if(cw+w[i] <= c){cw += w[i];Backtrack(i+1);cw -= w[i];}Backtrack(i+1);r+=w[i];//如果得不到最优解，再取消当前的集装箱，表⽰未选，因此剩余容量要再加上当前集装箱重量}template <class Type>Type MaxLoading(Type w[],Type c,int n){Loading<Type> X;X.w = w;X.c = c;X.n = n;X.bestw = 0;X.cw = 0;X.r = 0;for(int i=1;i<=n;i++)//计算总共的剩余集装箱重量X.r += w[i];X.Backtrack(1);return X.bestw;}构造最优解： 为了构造最优解，必须在算法中保存最优解的记录。

最佳调度问题（回溯法）⼀、实验内容运⽤回溯法解决0-1背包问题（或装载问题、或批处理作业调度、或旅⾏售货员问题）使⽤回溯法解决批处理作业调度问题⼆、所⽤算法基本思想及复杂度分析1.算法基本思想从⼀条路往前⾛，能进则进，不能进则退回来，换⼀条路再试。

确定了解空间的组织结构后，回溯法从根节点出发，以深度优先搜索⽅式搜索整个解空间。

回溯法以这种⼯作⽅式递归地在解空间中搜索，直到找到所要求的解或解空间所有解都被遍历过为⽌。

2.问题分析及算法设计问题分析：（1）给定n个作业的集合{J1,J2,…,Jn}。

每个作业必须先由机器1处理，然后由机器2处理。

作业Ji需要机器j的处理时间为tji。

（2）对于⼀个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。

（3）所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。

（4）批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度⽅案，使其完成时间和达到最⼩。

算法设计：算法复杂度分析由于回溯算法在每⼀个结点处耗费O(1)计算时间，故在最坏情况下，整个算法的时间复杂性为O(n!).三、源程序核⼼代码及注释（截图）四、运⾏结果五、调试和运⾏程序过程中产⽣的问题及解决⽅法，实验总结（5⾏以上）调试和运⾏程序时没有多⼤的问题，主要是调试的步骤多，容易看错，从⽽理解错，解决⽅法：我是为每⼀个变量都添加了监视，⼀个⼀个的调试下去，再结合⾃⼰画的草图，⼀个的去分析，当正确的分析出⼀个分⽀后，就会发现，后⾯基本上都是重复的实现着前⾯的基本操作。

经过这次实验对于回溯法解问题时，⾸先应该明确问题的解空间，⼀般说来，解任何问题都有⼀个⽬标，在约束条件下使⽬标达到最优的可⾏解称为该问题的最优解。

#include<bits/stdc++.h>using namespace std;int n, k;int a[25];//任务完成的时间int x[25];//当前任务完成的时间int result = 410;//完成全部任务的最早时间void Backtrack(int num, int t){if (num > n)//到达叶⼦节点{if (t < result){//将最少时间赋值给resultresult = t;}}if (t >= result){//当⼤于时，直接跳出递归return;}for (int i = 0; i < k; i++){if (x[i] + a[num] < result){//看是否剪枝//当前任务完成时间+前⾯任务完成时间⼩于总时间时x[i] += a[num];//继续搜索下去Backtrack(num + 1, max(t, x[i]));//回溯x[i] -= a[num];//返回最初的状态}}}int main(){cin >> n >> k;for (int i = 0; i < n; i++){cin >> a[i];}Backtrack(0, 0);cout << result << endl;return 0;}。

实验4、《回溯法实验》一、实验目的1. 掌握回溯算法思想2. 掌握回溯递归原理3. 了解回溯法典型问题二、实验内容1. 编写一个简单的程序，解决8皇后问题。

2. 批处理作业调度问题[问题描述]给定n个作业的集合J=(J1, J2, … , Jn)。

每一个作业Ji都有两项任务需要分别在2台机器上完成。

每一个作业必须先由机器1处理，然后再由机器2处理。

作业Ji需要机器i的处理时间为tji，i=1,2, … ,n; j=1,2。

对于一个确定的作业调度，设Fji是作业i在机器i上完成处理的时间。

则所有作业在机器2上完成处理的时间和成为该作业调度的完成时间和。

批处理作业调度问题要求对于给定的n个作业，制定一个最佳的作业调度方案，使其完成时间和达到最小。

要求输入：1）作业数 2）每个作业完成时间表：作业完成时间机器1 机器2作业1 2 1作业2 3 1作业3 2 3要求输出： 1）最佳完成时间 2）最佳调度方案提示：算法复杂度为O(n!),建议在测试的时候n值不要太大，可以考虑不要超过12。

3. 数字全排列问题任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。

如N=3时，共有以下6种排列方式：123，132，213，231，312，321。

注意：数字不能重复，N由键盘输入（N<=9）。

三、算法思想分析1.八皇后问题是典型的回溯问题，先从空格子起逐行放皇后，如果符合要求即安全则放置，否则返回上一行下一个位置继续，直至最后一行安全放置则为一种放置方式。

2.批处理作业调度的解空间为排列数，不断利用递归函数直至叶节点，剪枝函数为当前用时与最佳用时的比较。

关于时间的计算，每次选择作业后先将机器1用时累加，机器2上总用时需要先比较上一个作业完成时间与此时机器1上的总用时，如果机器1上总用时大于上一作业用时，那么机器2上用时则加上机器1上用时与此作业在机器2上的单独用时，反之，则代表此时机器2仍然在处理上一任务，那么机器2上用时则加上上一作业用时与此作业在机器2上的单独用时。

回溯法——装载问题问题描述： 有⼀批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量是wi，且不能超，即Σwi<=c1+c2。

算法思想： ——在给定的装载问题有解的情况下 最优装载⽅案：⾸先将第⼀艘轮船尽可能的装满； 然后将剩余的集装箱装上第⼆艘轮船。

将第⼀艘轮船尽可能的装满等价于选取全体集装箱的⼀个⼦集，使该⼦集中集装箱重量之和最接近c1。

算法设计： 先考虑装载⼀艘轮船的情况，依次讨论每个集装箱的装载情况，共分为两种，要么装(1)，要么不装(0)，因此很明显其解空间树可以⽤⼦集树来表⽰。

在算法Maxloading中，返回不超过c的最⼤⼦集和，但是并没有给出到达这个最⼤⼦集和的相应⼦集，稍后完善。

在算法Maxloading中，调⽤递归函数Backtrack(1)实现回溯搜索。

Backtrack(i)搜索⼦集树中的第i层⼦树。

在算法Backtrack中，当i>n时，算法搜索到叶结点，其相应的载重量为cw，如果cw>bestw，则表⽰当前解优于当前的最优解，此时应该更新bestw。

算法Backtrack动态地⽣成问题的解空间树。

在每个结点处算法花费O(1)时间。

⼦集树中结点个数为O(2^n)，故Backtrack所需的时间为O(2^n)。

另外Backtrack还需要额外的O(n)的递归栈空间。

算法描述：1 template <class Type>2class Loading3 {4 friend Type MaxLoading(Type [],Type,int);5private:6void Backtrack(int i);7int n; //集装箱数⽬8 Type * w, //集装箱重量数组9 c, //第⼀艘轮船的载重量10 cw, //当前载重量11 bestw; //当前最优载重量12 };1314 template <class Type>15void Loading<Type>::Backtrack(int i) //回溯搜索16 { //搜索第i层结点17if(i>n) //到达叶结点18 {19if(cw>bestw)20 bestw = cw;21return;22 }23if(cw+w[i] <= c) //搜索⼦树24 {25 cw += w[i]; //当前载重量增加正考虑对象的重量26 Backtrack(i+1);　27 cw -= w[i]; //递归返回上⼀层时，记得减去刚考虑对象的集装箱重量28 }29 Backtrack(i+1); //递归搜索第i+1层30 }3132 template <class Type>33 Type MaxLoading(Type w[],Type c,int n) //返回最优载重量34 {35 Loading<Type> X; //初始化36 X.w = w;37 X.c = c;38 X.n = n;39 X.bestw = 0; //当前最优载重量的初值赋为040 X.cw = 0;41 X.Backtrack(1); //计算最优载重量————调⽤递归函数，实现回溯搜索42return X.bestw;43 }上界函数： 引⼊剪枝函数，⽤于剪去不含最优解的⼦树：即当cw(当前载重量)+r(未考察对象的总重量)<bestw(当前的最优载重量)时当前⼦树不可能包含最优解，直接减掉。

算法分析与设计实验报告第五次附加实验cp += p[i];Backtrack(i+1); //回溯//回溯结束回到当前根结点cw -= w[i];cp -= p[i];}//进入右子树，条件是上界值比当前最优值大，否则就将右子树剪掉if(Bound(i+1)>bestp){Backtrack(i+1);}}测试结果当输入的数据有解时：当输入的数据无解时：当输入的数据稍微大点时：附录：完整代码（回溯法）//0-1背包问题 回溯法求解 #include <iostream> using namespace std;template <class Typew,class Typep>class Knap //Knap 类记录解空间树的结点信息 {template <class Typew,class Typep>friend Typep Knapsack(Typep [],Typew [],Typew,int ); private :Typep Bound(int i); //计算上界的函数void Backtrack(int i); //回溯求最优解函数实验分析在实验中并没有生成多组数据，进行比较，也没有利用随机生成函数，因为在这种有实际有关联的问题中，利用随机生成函数生成的数据是十分的不合适的，在此我们只需要验证该程序是否正确即可。

0-1背包问题和之前的最优装载其实质上一样的，都是利用解空间树，通过深度优先搜索子集树，通过利用上界函数和一些剪枝策略，从而得到最优解。

由于数据较小，所以时间上并不能反映出什么东西。

实验心得在这一章的回溯算法中，我们用的比较多的就是；利用子集树来进行问题的探索，就例如上图是典型的一种子集树，在最优装载、0-1背包都是利用了这种满二叉树的子集树进行求解，然后通过深度优先的策略，利用约束函数和上界函数，将一些不符合条件或者不包含最优解的分支减掉，从而提高程序的效率。

回溯法：最⼤装载问题（使⽤递归，不做任何优化）// 16x1.cpp : Defines the entry point for the console application.//#include "stdafx.h"// 回溯法，解空间分为排列数和⼦集树，前者是不同节点顺序的排列，后者是⼀个(0,1,...)的向量⼦集// 最⼤装载问题，是⼀个NP问题，⽬前只计算第⼀艘船，属于⼦集树// 有⼏个货物，⼦集树就有⼏层，当前题⽬为5层// 我感觉递归还是太过于精巧和经凑，很难挖空⼼思⾃⼰写出来，多熟悉别⼈现有的程序是⼀个好办法。

#include<iostream.h>template<class T>class Loading {friend GetMaxLoading(T [], T, int);private:void Compute(int i);int n; // 货箱数量T *w, // 货箱重量数组c, // 第⼀艘船的容量cw, // 当前的装载重量bestw; // ⽬前最优装载重量};// 重要特性：在遍历的时候，就得到了结果。

使⽤全局变量保存了最⼤装载值// 此函数⼀共只有⼀处return// 运算过程：// 第⼀、第⼆层能放下货物，⾛的是if语句的条件分⽀，然后开始计算第三层。

// 第三层因为不满⾜if语句条件，直接⾛的是if语句后⾯的语句，什么值都不改变。

// 第四、第五层直接⾛的是if语句后⾯的语句，什么值都不改变。

// 第六层返回，于是第五、第四、第三都直接返回，相当于第⼆层的Compute(i+1);语句计算完毕（但第⼆层整个过程没有计算完毕，后⾯还有其它语句）// 此时，相当于第⼆层x=1的情况的⼦树计算完毕了，但还要在这层继续计算x=0的⼦树。

// 所以把当前cw值恢复成不装当前货物时候的值，即程序继续往下执⾏cw -= w[i];语句// 然后相当于，在第⼆层不装货物的情况下，开始遍历计算第三层的值。

将n个集装箱装上载重量为c1和c2的轮船，其中集装箱总重量<c1+c2,使用回溯法求出最优装载方案。

二、实验流程图：input.txtoutput.txt四、源程序：package javaapplication1; import java.io.*;public class Main { static int n;static int []w;static int c1,c2;static int cw;static int bestw;static int r;static int []x;static int []bestx;public static int maxloading(int[]ww,int cc,int[]xx){w=ww;c1=cc;bestw=0;cw=0;x=new int[n+1];bestx=xx;r=0;for(int i=1;i<=n;i++)r+=w[i];backtrack(1);return bestw;}private static 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];if(cw+w[i]<=c1){x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}if(cw+r>bestw){x[i]=0;backtrack(i+1);}r+=w[i]; }public static void main(String[] args) throws IOException {BufferedReader read =new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));String a=new String();a=read.readLine();n=Integer.parseInt(a);System.out.println("集装箱个数: "+n);x=new int[n+1];String[]b=new String[n];a=read.readLine();System.out.println("集装箱重量: "+a);b=a.split(",");w=new int[n+1];for(int i=1;i<=n;i++){w[i]=Integer.parseInt(b[i-1]);}a=read.readLine();c1=Integer.parseInt(a);a=read.readLine();c2=Integer.parseInt(a);System.out.println("轮船载重量: "+c1+","+c2);int result= maxloading(w,c1,x);int max,temp;for(int i=1;i<3;i++){for(int j=2;j<3;j++){if(w[i]>w[j]){temp=w[i];w[i]=w[j];w[j]=temp;}}}if((w[3]>c1)&&(w[3]>c2)){System.out.println("都不可装");}else{System.out.println("轮船1装载的集装箱：");for (int u=1;u<n+1;u++)if(bestx[u]==1)System.out.println(u+" ");if(r>(result+c2))System.out.println("轮船1可装："+result+" "+"轮船2装不完.");else{System.out.println("轮船2装载的集装箱：");for (int u=1;u<n+1;u++)if(bestx[u]==0)System.out.println(u+" ");System.out.println("最优装载--轮船1:"+result+" "+"轮船2:"+(r-result));}}PrintWriter print=new PrintWriter(new OutputStreamWriter(new FileOutputStream("output.txt")));if((w[3]>c1)&&(w[3]>c2)){print.println("都不可装。