四种基本算法思想

发表于 2020-10-26 更新于 2024-09-17 分类于 Algorithm Waline：

数据结构与算法是一个非常大的范围，各种不同的问题需要不同的算法，这些算法或复杂或简单。这篇博客简单通过经典的背包问题介绍四种非常基本且常用的算法思想，分别是贪心，分治，回溯，动规。

这四种是算法思想，不是具体的算法，主要是理解其思路，而不是具体的实现。

这篇文章主要是帮我我把以前略显零散的知识点重新总结一下，所以很多具体内容在以前的其他博客中。

假设我们有一个可以容纳 100kg 物品的背包，可以装各种物品。我们有以下 5 种豆子，每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？

贪心

实际上，这个问题很简单，我估计你一下子就能想出来，没错，我们只要先算一算每个物品的单价，按照单价由高到低依次来装就好了。单价从高到低排列，依次是：黑豆、绿豆、红豆、青豆、黄豆，所以，我们可以往背包里装 20kg 黑豆、30kg 绿豆、50kg 红豆。

这个问题的解决思路显而易见，它本质上借助的就是贪心算法。结合这个例子，我总结一下贪心算法解决问题的步骤，我们一起来看看。

第一步，当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。

类比到刚刚的例子，限制值就是重量不能超过 100kg，期望值就是物品的总价值。这组数据就是 5 种豆子。我们从中选出一部分，满足重量不超过 100kg，并且总价值最大。

第二步，我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。

类比到刚刚的例子，我们每次都从剩下的豆子里面，选择单价最高的，也就是重量相同的情况下，对价值贡献最大的豆子。

第三步，我们举几个例子看下贪心算法产生的结果是否是最优的。大部分情况下，举几个例子验证一下就可以了。严格地证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。而且，从实践的角度来说，大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明。

贪心算法工作的前提是前一步的选择不会影响下一步的选择，比如刚才这个问题，如果我加了限制，选了黄豆就不能选绿豆，这个题目用贪心算法就没法解决了。

我们稍微改造下刚才的背包问题，变成0-1背包问题：

我们有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

实际上，背包问题我们在贪心算法那一节，已经讲过一个了，不过那里讲的物品是可以分割的，我可以装某个物品的一部分到背包里面。今天讲的这个背包问题，物品是不可分割的，要么装要么不装，所以叫 0-1 背包问题。显然，这个问题已经无法通过贪心算法来解决了。我们现在来看看，用回溯算法如何来解决。

回溯是一种思想，往往与递归这种编程技巧配合使用。

回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。

为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

具体解释可以看这篇博客：https://sunra.top/posts/376d0826/

其实片面点讲，回溯就是在深度优先遍历的过程中记录下来你走过了哪些节点，而到达叶子节点的条件是满足是没有其他路可以选了，就开始回溯。

动态规划如果从递归的角度讲，其实也不是一个非常难懂的思想，上面讲的回溯说的是在遍历过程中记录下走过的路径，那么动态规划就是一个带备忘录的递归过程，换种说法，如果递归过程中有重复子问题，就用动态规划，没有那就回溯。

比如我在递归过程中选择前四种豆子的最优解是选择前三种和选择前两种最优解的一个函数，即dp(4) = f(dp(3), dp(2))，一旦我计算出dp(4)，我先找个地方把它存下来，等我计算dp(5)的时候需要用到dp(4)，我就不需要继续递归了。

而把这个递归过程转化为递推公式，就是动态规划了。

具体可以参考这里：https://sunra.top/posts/a80d0031/

分治算法（divide and conquer）的核心思想其实就是四个字，分而治之，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

这个定义看起来有点类似递归的定义。关于分治和递归的区别，我们在排序（下）的时候讲过，分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：

分治算法能解决的问题，一般需要满足下面这几个条件：

归并排序就是一个非常典型的分治思想