软考-软件设计师：算法策略：分治法、贪心法、动态规划法、回溯法 作者：马育民 • 2025-04-15 11:24 • 阅读：10004 **提示：**本文讲解算法策略中主要的4个策略，而且 分治法、贪心法、动态规划法有些类似 # 分治法 用于较复杂的问题，必须可以逐步被分解为容易解决的独立的子问题，这些子问题解决后，进而将它们的解“合成”，就得到较大问题的解，最终合成为总问题的解。 ### 特征 把一个问题拆分成 **多个小规模** 的 **相同子问题**，一般用 **递归** 解决 - **分解：**该问题可以分解为若干个 **规模较小**、相互独立，**与原问题类似** 的子问题 - **解决：**解决各个子问题 - **合并：**将各个子问题的解，合并为该问题的解 ### 代码特点 会用到 **递归** >递归：就是在函数中，调用自己 ### 经典问题 - **斐波那契数列** - `归并排序`，没有分解，只用到把小问题的解，合并成该问题的解 - `快速排序` - 矩阵乘法 - `二分查找（搜索）` - 大整数乘法 - 汉诺塔 ### 案例 - 求斐波那契 [](https://www.malaoshi.top/upload/0/0/1GWwwqrygAK.png) # 贪心法（一般用于求满意解） ### 特征 局部最优，但整体不见得最优。每步有明确的、既定的策略。 ### 审题技巧 没有明确的文字特征，可能有 **关注现在** 字样，如果做题时，遇到这种情况，一般是贪心法 ### 经典问题 - 背包问题页（如装箱） - 多机调度 - 找零钱问题 - **最小生成树问题(普里姆算法、克鲁斯卡尔算法)** ### 案例 - 部分背包问题 [](https://www.malaoshi.top/upload/0/0/1GWwxPgS6OL.png) 如上图： 有一个背包，背包容量是 `70` 有 `3` 个物品： - 物品1，重量 `20`，价值 `140` - 物品2，重量 `30`，价值 `180` - 物品3，重量 `40`，价值 `200` 物品可以 **分割成任意大小**。要求尽可能让装入背包中的物品 **总价值最大**，但不能超过总容量。 **实现方式一（局部最优、整体不是最优）：** 计算出各个物品的单价，即：`单价 = 价格 / 重量`，将 **单价 最高** 的物品装起来，此时 **局部最优** - 物品1，单价 `7` - 物品2，单价 `6` - 物品3，单价 `5` `物品1`、`物品2` **单价 最高**，且总重量不超过背包限制，将其装入到背包，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwxRXEYWD.png) **缺点：** - 局部最优：放入的物品都是单价最高的 - 整体不是最优：如果放入 `物品2`、`物品3`，总价值是 `380`，超过本方法的价值 **实现方式二（局部最优、整体不是最优）：** 将 **价值 最高的物品** 装起来，此时 **局部最优** - 物品1，重量 `20`，价值 `140` - 物品2，重量 `30`，价值 `180` - 物品3，重量 `40`，价值 `200` `物品2`、`物品3` 价值最高，且总重量不超过背包限制，将其装入到背包，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwxWT7wgT.png) **缺点：** - 局部最优：放入的物品价值最高 - 整体不是最优：见实现方法三 **实现方式三（最优）：** 计算出各个物品的单价，即：`单价 = 价格 / 重量`，将 **单价 最高** 的物品装起来，此时 **局部最优** - 物品1，单价 `7` - 物品2，单价 `6` - 物品3，单价 `5` `物品1`、`物品2` **单价 最高**，且总重量不超过背包限制，将其装入到背包，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwxRXEYWD.png) 还空出 `20` 的容量，将 `物品3` 分割一半，放入进去，如下： [](https://www.malaoshi.top/upload/0/0/1GWwxbUYuhd.png) **此时才是最优解** # 动态规划法（用于求最优解）考的多 ### 特征 划分子问题，使用数组存储子问题结果，利用查询子问题结果构造最终问题结果。 >与贪心、分治法类似 ### 审题技巧 如果提到 `最优子结构` 和 `递归式` 字样，说明是 `动态规划法` ### 有两种实现方式 - 自顶向下 - 自底向上 ### 实现方式一：自顶向下 **特点：**用到递归 如：斐波那契 ``` f(100) + f(99) + f(98) + f(97) + ... + f(1) ``` **注意：**自顶向下，到底后，还要向上执行，所以时间复杂度比 `自底向上` 大 **时间复杂度：**$$O(2^n)$$ ### 实现方式二：自底向上 **特点：**用到数组（一维、二维...） 如：计算二维数组的某种结果，需要用到双重循环 ``` arr[0][0] arr[0][1] arr[0][2] .... arr[m][n] ``` **时间复杂度：** $$O(n^a)$$ ( `a`：几重循环就是几) ### 经典问题 斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列 # 回溯法 ### 特征 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。 但当搜索到某一步时，发现原先选择并不优或达不到目标，就 **退回一步** 重新选择。 这种 **走不通就退回**，重新选择就是回溯法。 **审题技巧** 有 `前进`、`后退` 字样 ### 代码特点 当前元素是 $$K\_n$$ ( `n` 是下标)： - 正常处理 $$K\_n$$ 后，继续处理下一个点，代码会执行：`n + 1` - 不能处理，回溯到上一个点，代码会执行：`n - 1` ### 经典问题 N皇后问题、迷宫、背包问题、图的遍历（回溯法对解空间做深度优先探索，分支限界法对解空间做广度优先探索） # 算法策略间的关系 ### 对问题进行分解的算法策略 - 分治法与动态规划法 **共同点：** 1. 分治法与动态规划法实际上都是递归思想的运用。 2. 二者的根本策略都是对问题进行分解，找到大规模与小规模的关系，然后通过解小规模的解，得出大规模的解。 **不同点：** 适用于分治法的问题分解成子问题后，各子问题间无公共子子问题； 而动态规划法相反，如下： ``` 动态规划法 = 分治算法思想 + 解决子问题间的冗余情况。 ``` ### 多阶段逐步解决问题的策略 - 贪心算法和动态规划法 **贪心算法：**每一步都根据策略得到一个结果，并传递到下一步，自顶向下，一步一步地做出贪心决策。 **动态规划算法：**每一步决策得到的不是一个唯一结果，而是一组中间结果（且这些结果在以后各步可能得到多次引用），只是每一步都使问题的规模逐步缩小，最终得到问题的一个结果。 # 题 采用贪心算法保证能求得最优解的问题是 A、0-1背包 B、矩阵链乘 C、最长公共子序列 D、部分（分数）背包 ### 分析 0-1背包：要么都装下，要么都不装 ### 答案 D # 题 [](https://www.malaoshi.top/upload/0/0/1GWwxgmK7hp.png) [](https://www.malaoshi.top/upload/0/0/1GWwxqnT2zE.png) [](https://www.malaoshi.top/upload/0/0/1GWwy3Ypnom.png) ### 第一问答案 题目指出使用 `快排` 算法，属于 `分治法` ### 第二问答案 没有明确文字特征，说明是贪心算法 ### 第三问答案 快排时间复杂度：`O(nlog₂n)` 但题目明确指示重复 2、3、4 步骤，需要使用双重循环，时间复杂度是 `O(n²)` 最终时间复杂度选最大的，即：`O(n²)` ### 第四问答案 ##### 画图法实现 **优缺点：**直观，但费劲，耗时间 通过下面画表格（或画线）可知： - 活动1、2、3、4、5，各占一个场地 - 活动6 与 活动2不冲突 - 活动7 与 活动4不冲突（题中已经给出） - 活动8 与 活动1不冲突（题中已经给出） - 活动9 与 活动5不冲突（题中已经给出） - 活动10 与 活动6不冲突 - 活动11 肯定不冲突 所以共需要占用 `5` 个场地 [](https://www.malaoshi.top/upload/0/0/1GWwyRurVoq.png) ##### 数字表示 **优缺点：**省事，不直观 ``` 活动1时间：(0,6) 活动2时间：(1,4) 活动3时间：(2,13) 活动4时间：(3,5) 活动5时间：(3,8) 活动6时间：(5,7) 活动7时间：(5,9) 活动8时间：(6,10) 活动9时间：(8,11) 活动10时间：(8,12) 活动11时间：(12,14) ``` - 活动1、2、3、4、5，各占一个场地 - 活动6 与 活动2不冲突 - 活动7 与 活动4不冲突（题中已经给出） - 活动8 与 活动1不冲突（题中已经给出） - 活动9 与 活动5不冲突（题中已经给出） - 活动10 与 活动6不冲突 - 活动11 肯定不冲突 # 题 [](https://www.malaoshi.top/upload/0/0/1GWwyoXikda.png) [](https://www.malaoshi.top/upload/0/0/1GWwyo93LaX.png) ### 第一问答案 因为提到 **最优子结构**，所以是 `动态规划法` ### 第二问答案 通过递归式 公式 `m[i,j]` 可知是二维数组，遍历需要两重循环 里面有 `min操作`(`i<=k<=j`)，在上面两重循环中，再循环 三重循环，所以时间复杂度：`O(n³)` ### 第三问答案 自底向上执行，而且是对矩阵操作，所以用到二维数组存储数据，所以空间复杂度：`O(n²)` ### 第四问答案 耗时耗力且分值低，放弃 参考： https://blog.csdn.net/qq_34489943/article/details/79761498 原文出处：http://malaoshi.top/show_1GWx13Za101.html