39 | 回溯算法：从电影《蝴蝶效应》中学习回溯算法的核心思想

回溯算法本质上就是枚举，优点在于其类似于摸着石头过河的查找策略，且可以通过剪枝少走冤枉路。它可能适合应用于缺乏规律，或我们还不了解其规律的搜索场景中。

0-1背包问题理解： 假设三个物品，每个物品在考虑时有两种选择，1-放进包，0-不放 11行代码表示不放进包里。13行代码表示放进包里。 三个物品遍历过程如下： 0 0 0 update maxW 0 0 1 update maxW 0 1 0 update maxW 0 1 1 update maxW 1 0 0 update maxW 1 0 1 update maxW 1 1 0 update maxW 1 1 1 update maxW

回溯就是暴力枚举的解法吧？遍历所有情况，当满足情况就停止遍历（剪枝）。

看不懂背包问题代码同学，请好好仔细看看下面这句话，再结合代码你就看懂了 我们可以把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。

老师，我经过查资料，找到，其实判断是否在一条斜线上还有更加简便的做法，就是如果行互减的绝对值等于列互减的绝对值，那么就是在一条斜线上的。 if (Math.abs(row - i) == Math.abs(column - result[i])) { return false; }

我今天也把8皇后写出来了 虽然是第一次

这个回塑问题，老师讲的的理解了，但总感觉还是哪里没有学会，我又说不出来，好像总觉得少了点什么？ 老师关于课后的题目，0-1背包，在限制重量与数量的前提下，这个解我觉得其实挺简单的，就是把老师的那个代码稍加改造就OK了 public void countMaxPkg( int index, int sumValue, int sumWeight, PkgValue[] items, int maxNum, int maxWeight) { // 1,如果当前重量到达最大总重量，或者数量达到最达限制，则设置当前最大值 if (index == maxNum || sumWeight == maxWeight) { // 检查总重量是否更重 if (sumMaxWeight < sumWeight) { sumMaxWeight = sumWeight; } // 检查当前价值是否更大 if (maxValue < sumValue) { maxValue = sumValue; } return; } // 针对每个物品，有当前不加入背包中计算价值 countMaxPkg(index + 1, sumValue, sumWeight, items, maxNum, maxWeight); // 当前的最大总重量还是要小于限制值 if (sumWeight + items[index].getWeight() <= maxWeight) { // 针对每个物品，有当前加入背包计算价值 countMaxPkg( index + 1, sumValue + items[index].getValue(), sumWeight + items[index].getWeight(), items, maxNum, maxWeight); } } 完整代码在: https://github.com/kkzfl22/datastruct/blob/master/src/main/java/com/liujun/datastruct/algorithm/backtrackingAlgorithm/packageZoneOne/PackageValue.java 如果有问题，还请老师给予指正，谢谢！

正则匹配这个，*代表匹配任意个任意字符，那只要匹配到* 就可以直接返回matched=true吧，不用再递归了吧

aab c*a*b 正则表达式，能匹配通过，文章的代码通过不了，代码有问题

老师思考题应该就是下章的动态规划了吧。