【算法】贪心算法解析：基本概念、策略证明与代码例题演示
文章目录
- 1. 什么是贪心算法？
- 2. 贪心算法的特点
- 3. 例题（贪心策略）
- ① 找零问题
- ② 最小路径和
- ③ 背包问题
- 4. 贪心策略证明
1. 什么是贪心算法？
在学习贪心算法之前，一定要理解的是贪心策略：
贪心策略是一种根据具体问题而定的策略：其由局部优先 -> 全局有限，解释如下
- 把解决问题的办法分为若干步；
- 解决每一步的时候，都选择目前看起来 “最优” 的解法
- 最后结果希望得到最优解
2. 贪心算法的特点
贪心算法的特点，可以先看下面的例题再来理解就很轻松了。
-
贪心策略提出
- 贪心策略并没有 标准模板
- 根据具体题目而提出具体的策略
-
贪心策略的正确性
- 贪心策略得出的结果可能是错误的
- 正确的贪心策略，需要由我们证明的
3. 例题（贪心策略）
① 找零问题
假设有50元，买了六元的东西，需要找零44元。你有以下序列的纸币[20,10,5,1]（每张面值的纸币有无限多个），要求你用最少的纸币张数进行找零。
我们以贪心策略去思考这个问题：要尽可能的选面值大的纸币找零，即为贪心，则
46 = 20+20+5+1。
根据贪心算法最终选择了四张纸币，不难看出该选择就是最佳选择。
② 最小路径和
有下面一个矩阵，我们处于矩阵左上角，目的地为右下角，希望得到最小路径和。所走的方向只有→和↓两种方向。
根据贪心策略：因为题目要求最小路径和，则我们每次走当前看到的最小数值的位置，则如下图所示，最终路径和为 1+1+6+2+1=11。而最佳路径显然为1+3+1+1+1=7。
③ 背包问题
看下面的表格，有以下物品，分别有重量和价值两个指标（重量与价值成正相关），每个商品有无穷多个。
我们有一个 承重为10的背包，希望得到背包装的总价值最高的装法。
| 物品1 | 物品2 | 物品3 | |
|---|---|---|---|
| 重量 | 6 | 5 | 1 |
| 价值 | 12 | 9 | 1 |
由于这道题对我们装法的影响因素有两个，重量和价值，所以贪心策略可以分多种进行：
- 只看重量：为了获得更高价值的东西，我们需要尽可能多的物体，则选择重量更小的物品，则在背包承重范围内我们最终选择的总价为：1+1+…+1(n=10)=10
- 只看价值：我们尽可能去选择价值高的物品，则最终价格为：12+1+1+1+1=16
- 看单位重量价值：通过下面的计算，我们可以计算出每个物品的单位重量价值，则贪心策略为选择单位价值最高的物品，最后总价为：12+1+1+1+1 = 16
但实际上，根据三种贪心策略得出的结果都不是最佳选择，最佳策略为，选两个重量为5的物品，总价值为18。
我们会发现，由贪心策略得出的结果，对于例二例三都是错误的，而例一找零问题是正确的，实际上，当我们将找零问题的数据进行改动，如需要找零36元，我们有以下面额的纸币[20, 18, 10, 5, 1]，按照之前的贪心策略，最终结果为，一共4张纸币，而最佳策略为选择两张面额18的纸币，一共需两张。
4. 贪心策略证明
我们知道：正确的贪心策略，需要由我们证明的。
那么如何证明呢？
答：我们学习数学时所使用了解过的证明方法通通可行；直接证明、反证、数学归纳…
这里我们就来证明 为什么例一中的找零问题是正确的
