第一章回溯法(习题二

0-1背包问题计科1班朱润华 2012040732方法1：回溯法一、回溯法描述：用回溯法解问题时，应明确定义问题的解空间。

问题的解空间至少包含问题的一个（最优）解。

对于0-1背包问题，解空间由长度为n的0-1向量组成。

该解空间包含对变量的所有0-1赋值。

例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。

物品i的重量是wi，其价值为vi，背包的容量为C。

问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。

二、回溯法步骤思想描述：0-1背包问题是子集选取问题。

0-1 背包问题的解空间可以用子集树表示。

在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。

当右子树中有可能含有最优解时，才进入右子树搜索。

否则，将右子树剪去。

设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。

当cp+r<=bestp时，可剪去右子树。

计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。

例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。

这4个物品的单位重量价值分别为[3,2,3,5,4]。

以物品单位重量价值的递减序装入物品。

先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。

由此得一个解为[1,0.2,1,1]，其相应价值为22。

0-1背包问题计科1班朱润华 32方法1：回溯法一、回溯法描述：用回溯法解问题时，应明确定义问题的解空间。

问题的解空间至少包含问题的一个（最优）解。

对于0-1背包问题，解空间由长度为n的0-1向量组成。

该解空间包含对变量的所有0-1赋值。

例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。

物品i的重量是wi，其价值为vi，背包的容量为C。

问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。

二、回溯法步骤思想描述：0-1背包问题是子集选取问题。

0-1 背包问题的解空间可以用子集树表示。

在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。

当右子树中有可能含有最优解时，才进入右子树搜索。

否则，将右子树剪去。

设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。

当cp+r<=bestp时，可剪去右子树。

计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。

例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。

这4个物品的单位重量价值分别为[3,2,3,5,4]。

以物品单位重量价值的递减序装入物品。

先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装的物品2。

由此得一个解为[1,,1,1]，其相应价值为22。

尽管这不是一个可行解，但可以证明其价值是最优值的上界。

python回溯法例题回溯法是一种常用的算法思想，用于解决各种组合优化问题，尤其在解决NP完全问题方面有着广泛的应用。

本文将通过一个具体的例题来介绍和解释python回溯法的实现过程。

任务名称：python回溯法例题问题描述：给定一个由不同整数组成的数组nums，编写一个函数，返回所有可能的排列组合。

解题思路：要解决这个问题，我们可以使用回溯法来生成所有可能的排列组合。

回溯法是一种通过试错的方式搜索解空间的算法。

具体来说，我们从问题的一个初始解开始，通过一系列的决策，逐步构建问题的解，如果在构建的过程中发现当前的解不符合要求，我们就回溯到上一个状态，重新进行决策。

在本例中，我们可以使用一个递归函数来实现回溯法。

我们定义一个辅助函数backtrack，它接受一个当前的排列，一个用于标记数字是否被使用的数组，以及一个用于存储所有解的结果数组。

在函数中，我们首先检查当前的排列是否已经包含了所有的数字，如果是的话，我们将当前的排列添加到结果数组中。

然后，我们遍历所有的数字，对于每一个数字，如果它没有被使用过，我们将其添加到当前的排列中，然后递归调用backtrack函数，继续构建下一个数字。

最后，我们将当前的数字从排列中移除，以便进行下一次决策。

下面是具体的代码实现：```pythondef permute(nums):def backtrack(curr_perm, used, result):if len(curr_perm) == len(nums):result.append(curr_perm[:])else:for i in range(len(nums)):if not used[i]:curr_perm.append(nums[i])used[i] = Truebacktrack(curr_perm, used, result)used[i] = Falsecurr_perm.pop()result = []used = [False] * len(nums)backtrack([], used, result)return result```我们可以使用这个函数来解决给定数组的排列组合问题。

回溯法习题汇总1.1 马拦过河卒源程序名knight.???（pas, c, cpp）可执行文件名knight.exe输入文件名knight.in输出文件名knight.out【问题描述】棋盘上A点有一个过河卒，需要走到目标B点。

卒行走的规则：可以向下、或者向右。

同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

因此称之为“马拦过河卒”。

棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

【输入】一行四个数据，分别表示B点坐标和马的坐标。

【输出】一个数据，表示所有的路径条数。

【样例】knight.in knight.out6 6 3 3 6【算法分析】从起点开始往下走(只有两个方向可以走)，如果某个方向可以走再继续下一步，直到终点，此时计数。

最后输出所有的路径数。

这种方法可以找出所有可能走法，如果要输出这些走法的话这种方法最合适了，但是本题只要求输出总的路径的条数，当棋盘比较大时，本程序执行会超时，此时最好能找出相应的递推公式更合适，详见后面的递推章节。

1.2 出栈序列统计源程序名stack1.???（pas, c, cpp）可执行文件名stack1.exe输入文件名stack1.in输出文件名stack1.out【问题描述】栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。

你已经知道栈的操作有两·种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。

现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。

请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。

【输入】一个整数n（1<=n<=15）【输出】一个整数，即可能输出序列的总数目。

回溯法作业答案1. 旅行商问题（作业实验)设有n个城市，城市之间道路的长度均大于或等于0，还可能是∞（对应城市之间无交通线路）。

一个旅行商从某个城市出发，要经过每个城市一次且仅一次，最后回到出发的城市，问他如何走才能使他走的路线最短？分析：旅行商问题对应的解的元组为n元组，其中假设第一个城市为1，则n元组中未确定的为剩下n-1个城市，元组为（1,x2,…,x n）,每个x i的取值为{2,…,n}；约束条件为已经经过的城市不能再走，最后回到出发城市。

算法：INPUT: n个城市分别为{1，2，…n},城市之间路径长度的矩阵d[i][j] 。

OUTPUT: 从城市1出发的最短巡回旅行路线及长度。

1. for k =1 to n2. c[k] =13. end for4. k =2,L=0,MinL=∞5. while k≥26. while c[k]≤n-17. c[k] =c[k]+18. L=L+d[c[k-1]][c[k]]9. if c为合法的thenMinL=min{MinL,L}, p[]=c[]10. else if c是部分解then11. if L>=MinL then continue12. else k =k+113. endif14. endif15. end while16. L=L-d[c[k-1]][c[k]]17. c[k] =118. k =k-119. end while20. output MinL, p[]2. 邮票问题(作业实验选做)设有已知面额的邮票m种（假设一定有面值为1的邮票；如果没有，连续值就从最小面额的邮票面额值开始），每种有n张，问用总数不超过n张的邮票进行组合，能组合的邮票面额中可以连续的面额数最多有多少？例如：n=4 m=3v1=1 v2=2 v3=4最后的解为14。

分析：第一种思路：邮票问题是从m种邮票中选择n张邮票，求所有可能取得的面额，最后在确定最大连续面额的值。

回溯算法经典问题请设计⼀个函数，⽤来判断在⼀个矩阵中是否存在⼀条包含某字符串所有字符的路径。

路径可以从矩阵中的任意⼀个格⼦开始，每⼀步可以在矩阵中向左，向右，向上，向下移动⼀个格⼦。

如果⼀条路径经过了矩阵中的某⼀个格⼦，则该路径不能再进⼊该格⼦。

分析：回溯算法这是⼀个可以⽤回朔法解决的典型题。

⾸先，在矩阵中任选⼀个格⼦作为路径的起点。

如果路径上的第i个字符不是ch，那么这个格⼦不可能处在路径上的第i个位置。

如果路径上的第i个字符正好是ch，那么往相邻的格⼦寻找路径上的第i+1个字符。

除在矩阵边界上的格⼦之外，其他格⼦都有4个相邻的格⼦。

重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。

由于回朔法的递归特性，路径可以被开成⼀个栈。

当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格⼦的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。

由于路径不能重复进⼊矩阵的格⼦，还需要定义和字符矩阵⼤⼩⼀样的布尔值矩阵，⽤来标识路径是否已经进⼊每个格⼦。

当矩阵中坐标为（row,col）的格⼦和路径字符串中相应的字符⼀样时，从4个相邻的格⼦(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下⼀个字符如果4个相邻的格⼦都没有匹配字符串中下⼀个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前⼀个，然后重新定位。

⼀直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置class Solution {public:bool hasPath(char* matrix, int rows, int cols, char* str){if(str==NULL||rows<=0||cols<=0)return false;bool *isOk=new bool[rows*cols]();for(int i=0;i<rows;i++){for(int j=0;j<cols;j++)if(isHsaPath(matrix,rows,cols,str,isOk,i,j))return true;}return false;}bool isHsaPath(char *matrix,int rows,int cols,char *str,bool *isOk,int curx,int cury){if(*str=='\0')return true;if(cury==cols){curx++;cury=0;}if(cury==-1){curx--;cury=cols-1;}if(curx<0||curx>=rows)return false;if(isOk[curx*cols+cury]||*str!=matrix[curx*cols+cury])return false;isOk[curx*cols+cury]=true;bool sign=isHsaPath(matrix,rows,cols,str+1,isOk,curx-1,cury)||isHsaPath(matrix,rows,cols,str+1,isOk,curx+1,cury)||isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury-1)||isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury+1);isOk[curx*cols+cury]=false;return sign;}};。

第5章回溯法回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。

当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。

如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。

在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。

扩大当前候选解的规模，以继续试探的过程称为向前试探。

回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。

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

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

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

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

换句话说，这个结点不再是一个活结点。

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

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

运用回溯法解题通常包含以下三个步骤： （1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；5.1〖案例1〗组合问题找出从自然数1、2、……、n 中任取r 个数的所有组合。

例如n=5，r=3的所有组合为：（1）1、2、3 （2）1、2、4 （3）1、2、5 （4）1、3、4 （5）1、3、5 （6）1、4、5 （7）2、3、4 （8）2、3、5 （9）2、4、5 （10）3、4、5则该问题的状态空间为：E={（x1，x2，x3）∣xi ∈S ，i=1，2，3}，其中：S={1，2，3，4，5} 约束集为：x1<x2<x3显然该约束集具有完备性。