2004 年上映了一部非常著名的电影《蝴蝶效应》，讲的就是主人公为了达到自己的目标，一直通过回溯的方法，回到童年，在关键的岔路口，重新做选择。当然，这只是科幻电影，我们的人生是无法倒退的，但是这其中蕴含的思想其实就是回溯算法。
深度优先搜索算法利用的是回溯算法思想，它除了用来指导像深度优先搜索这种经典的算法设计之外，还可以用在很多实际的软件开发场景中，比如正则表达式匹配、编译原理中的语法分析等。除此之外，很多经典的数学问题都可以用回溯算法解决，比如数独、八皇后、0-1 背包、图的着色、旅行商问题、全排列、正则表达式匹配等等。
回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。
回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。
回溯算法解决八皇后问题
有一个8x8的棋盘，希望往里面放8个棋子，每个棋子所在的行、列、对角线都不能有另一个棋子，求满足要求的所有摆放方式。
我们把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行、第三行……第八行。在放置的过程中，我们不停地检查当前放法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放法，继续尝试。
两个回溯算法的经典应用
0-1背包问题
假设有一个背包，背包的总的承载重量是Wkg，有n个物品，每个物品的重量不等，而且不可分割。现在期望选择几件物品，装在背包中，在不超过背包锁能承载重量的前提下，如何让背包中物品总的重量最大？
在贪心算法中举了一个物品可以分割的背包问题，即可以装某个物体的一部分到背包中，现在的问题是物品不可分割，要么装要么不装，显然这个问题无法通过贪心算法来解决。
对于每个物品都有两种选择，装进背包或者不装进背包，对于n个物品来说，总的装法就有种，去掉总重量超过Wkg的，从剩下的装法中选择重量最接近Wkg的。将整个问题分为n个阶段，每个阶段对应一个物品如何选择，先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。
正则表达式
我们依次考察正则表达式中的每个字符，当是非通配符时，我们就直接跟文本的字符进行匹配，如果相同，则继续往下处理；如果不同，则回溯。
如果遇到特殊字符的时候，我们就有多种处理方式了，也就是所谓的岔路口，比如“*”有多种匹配方案，可以匹配任意个文本串中的字符，我们就先随意的选择一种匹配方案，然后继续考察剩下的字符。如果中途发现无法继续匹配下去了，我们就回到这个岔路口，重新选择一种匹配方案，然后再继续匹配剩下的字符。
思考：
如果对0-1 背包问题稍加改造，如果每个物品不仅重量不同，价值也不同。如何在不超过背包重量的情况下，让背包中的总价值最大？
