回溯算法练习

发表于 更新于 分类于

回溯本质

回溯算法本质上是一种递归算法

一般用以解决下面的问题：

  • 组合问题：从n个数里按照某个规则找出k个数；
  • 切割问题：一个字符串按照一定的方法有几种切割方法；
  • 子集问题：n个数里有多少符合条件的子集；
  • 排列问题：n个数按照某种排列规则，有几种排列方法；
  • 棋盘问题：n皇后等等；

解决过程

回溯的问题都能使用树形结构来解决，就是在树形结构中进行递归查找，即：集合的大小构成了树的宽度，递归的深度就是树的深度。

递归一定是要有终止条件，所以回溯问题构成的树，一定是一个有限深度的树。

解决模版

回溯问题的解决模版：(回溯三部曲）

  1. 确定回溯函数的返回值及参数；
  2. 回溯函数的终止条件；
  3. 回溯搜索的遍历过程；
1
2
3
4
5
6
7
8
9
10
11
12
13
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

力扣实战

烹饪料理

欢迎各位勇者来到力扣城，城内设有烹饪锅供勇者制作料理，为自己恢 复状态。
勇者背包内共有编号为 0 ~ 4 的五种食材，其中 materials[j] 表示第 j 种食材的数量。通过这些食材可以制作若干料理，cookbooks[i][j] 表示制作第 i 种料理需要第 j 种食材的数量，而 attribute[i] = [x,y] 表示第 i 道料理的美味度 x 和饱腹感 y。
在饱腹感不小于 limit 的情况下，请返回勇者可获得的最大美味度。如果无法满足饱腹感要求，则返回 -1。
注意：
每种料理只能制作一次。

示例 1：

输入：materials = [3,2,4,1,2]
cookbooks = [[1,1,0,1,2],[2,1,4,0,0],[3,2,4,1,0]]
attribute = [[3,2],[2,4],[7,6]]
limit = 5

输出：7

解释：
食材数量可以满足以下两种方案：
方案一：制作料理 0 和料理 1，可获得饱腹感 2+4、美味度 3+2
方案二：仅制作料理 2， 可饱腹感为 6、美味度为 7
因此在满足饱腹感的要求下，可获得最高美味度 7

题目有点长，虽然题目整体难度不大，但还是有些注意点，我犯错了调试半天才发现。
结合前面的三部曲，

  1. 确定回溯函数的返回值及参数；
  2. 回溯函数的终止条件；
  3. 回溯搜索的遍历过程；

很快啊，我们就能确定返回值是一个 bestYummy(最大美味度 ，int数值)，随着递归深入，不断更新这个 值。

ok， 参数的话我们把题目里的条件都用上，多传递是没啥问题的，后面再优化嘛。

除了函数里已经给的 参数，我们需要传递 yummy(累计美味度, int类型) , 当前料理的id

ok 三部曲 第一部 完成

遇到id 为 n(总料理数，cookbooks.length) 结束循环， limit被用完更新最大值
ok 三部曲 第二部 完成

遍历过程比较重要，想象一下我们的树形结构，每层的决策都是一个二分，就是做或不做，to do or not to do 这个料理，ok， 我们就用两行递归代码搞定。
第一行递归是 not to do，为啥不是 to do，好问题～
第二行是to do，搞定这个to do前 需要去把相关的值做个更新，用于递归参数传递。

ok 至此 三部曲 第三部 完成

需要注意的点是，(敲黑板)

  1. 第二部曲 中， 结束循环 和 更新最大值的代码先后顺序！ 先更新再结束循环，否则最后一个料理如果是最优解的话就会错过～。～

  2. 第三部曲 中 递归传递的值发生更新的有 materials， yummy， id， limit， 需要注意的是materials的更新，它是一个数组，需要拷贝一份做修改，将修改的拷贝传入参数