【算法】贪心算法解析：基本概念、策略证明与代码例题演示

1. 什么是贪心算法？

在学习贪心算法之前，一定要理解的是贪心策略：

贪心策略是一种根据具体问题而定的策略：其由局部优先 -> 全局有限，解释如下

1. 把解决问题的办法分为若干步；
2. 解决每一步的时候，都选择目前看起来 “最优” 的解法
3. 最后结果希望得到最优解

2. 贪心算法的特点

贪心算法的特点，可以先看下面的例题再来理解就很轻松了。

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. 只看重量：为了获得更高价值的东西，我们需要尽可能多的物体，则选择重量更小的物品，则在背包承重范围内我们最终选择的总价为：1+1+…+1(n=10)=10
2. 只看价值：我们尽可能去选择价值高的物品，则最终价格为：12+1+1+1+1=16
3. 看单位重量价值：通过下面的计算，我们可以计算出每个物品的单位重量价值，则贪心策略为选择单位价值最高的物品，最后总价为：12+1+1+1+1 = 16

但实际上，根据三种贪心策略得出的结果都不是最佳选择，最佳策略为，选两个重量为5的物品，总价值为18。

我们会发现，由贪心策略得出的结果，对于例二例三都是错误的，而例一找零问题是正确的，实际上，当我们将找零问题的数据进行改动，如需要找零36元，我们有以下面额的纸币[20, 18, 10, 5, 1]，按照之前的贪心策略，最终结果为，一共4张纸币，而最佳策略为选择两张面额18的纸币，一共需两张。

4. 贪心策略证明

我们知道：正确的贪心策略，需要由我们证明的。

那么如何证明呢？
答：我们学习数学时所使用了解过的证明方法通通可行；直接证明、反证、数学归纳…

这里我们就来证明 为什么例一中的找零问题是正确的