C++ 基础算法 - 贪心算法

那么话不多说，今天我们来学习贪心算法

贪心是什么

所谓贪心，就是贪心 ( 废话 )，贪心就是贪，用较好的方式解决问题的一种方式，贪心很容易，因为不像其它算法一样需要记模板 ( 废话，没有模板 )；同时，贪心又很难，因为它需要其它算法的基础以及深入地思考如何贪以较优的方式解决问题，贪心类似于递推，都是从已知的部分像最终结果递进，在每一次都选择较优的结果

所以，贪心算法得满足最终结果可以通过局部的较优解求出并且最终结果能够被分解成多个部分且每个部分都能求出较优解

贪心算法

例如有这样一个非常经典的贪心问题，排队接水，有 n 个人排队接水，每个人都有需要的时间，而接水的地方只有 1 个水龙头，其中，每个人的接水时间 = 等待的时间 + 接水的时间，那么应该如何安排它们的接水顺序而使每个人的接水时间总和**小呢 ?

思考一下，如果让接水时间少的人先接水，那么后面等待的人中的等待时间这一个加数就会比接水时间多的人先接水少，所以应当让接水时间少的人先接水，而接水时间多的人后接水，这样排列下去，就能够确保总的接水时间为较优的

如果还没有想明白，可以这样想，如果先让接水时间多的人去接水，那么其它人的等待时间多会增加这个人的接水时间，也就是说，越后面的人，等待时间越久，因为接水的时间是不变的，已经由数据输入了的，所以等待时间缩小意味着总时间更短，所以只要先节水的人接水时间少，后面的人等待所花的时间就会少，这样一来就很有必要将接水时间少的人排在前面了

从这个问题可以看到，这里的贪心算法运用了排序算法，所以必须要有排序算法作为基础，这也是贪心算法的难点之一，如果其它的算法没有学好，就难以进步

当然这个问题属于是比较简单的，真正的贪心算法是各种贪思考才可以解出来的

当然，并不是每个题目都适合使用贪心算法，在一些题目中利用贪心算法将会是错误的，在使用贪心算法之前一定要先证明贪心算法所得的是较优解

怎么贪求局部较优解

贪心算法最重要的就是贪求局部较优解，可是这刚好又不太好想，在思考怎么贪时可以这么想，既然贪心就是从局部较优解出发，最终得到较优解，不妨从局部开始想，不去管这种方法是否为较优的方案，找到一个从局部中求较优解的方法，例如 1225：金银岛 这道题，既然背包有限，金属重量和金属价钱同时干扰我们进行判断，干脆将它们整合起来，变成性价比，将性价比较高的一种装进背包里，其它金属根本就不用管了，因为金属可以自由分割，也就不会有需要别的金属的时候了

到了这里，相信你已经会贪心算法了，贪心算法没有固定的模板，它本质上是一种思想，引导我们去找到局部问题的较优解，并拼凑起来，得到较优的答案

一本通平台的题解呢 ?被我吃了...

这次就先讲到这，下次补全题解