贪心算法

1. 前言

本节内容是贪心算法系列之一：贪心算法的介绍，主要介绍了贪心算法的定义，贪心算法的使用条件，明确了什么样的问题适合用贪心算法求解，最后说明贪心算法在日常生活中的应用场景。

贪心算法（Greedy Algorithm）是计算机科学与技术领域中一种常见的选择算法，与之前介绍的动态规划算法有一定的相似度。

顾名思义，贪心算法总是会做出在当前情况下看来最好的选择，谓之贪心，也就是说贪心算法并不会从整体最优考虑，它所做出的选择都只是在某种意义上的局部最优选择。当然贪心算法虽然不能对所有的问题得出整体最优解，但是在很多问题中还是有着很好的应用，可以得到整体的最优解。

贪心算法与动态规划算法的最大区别在于：贪心算法每次选择的时候都是按照贪心策略来选择的，满足当前情况的最优解，但是并不一定会是整体最优解；动态规划算法在选择考虑时会考虑所有的子情况，选择最优解，这会是整体的最优解。

首先，在利用贪心算法求解问题之前，我们需要清楚什么样的问题适合用贪心算法求解。一般而言，能够利用贪心算法求解的问题都会具备以下两点性质：

贪心选择： 当某一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次做出的选择可以依赖以前做出的选择，但不需要依赖后面需要做出的选择。这就是贪心选择性质。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

贪心算法与动态规划算法求解的问题类似，都需要满足最优子结构的性质。

在日常的生活学习中，贪心算法一般可以用来解决很多实际问题。现在，我们就来看看贪心算法具体有哪些应用场景。

场景 1：活动选择问题

假如小明是一个勤工俭学的在校生，每天可以兼职的时候有 10 个小时，然后现在学校有多个不同的兼职岗位，每个岗位有个开始时间和结束时间，小明在同一时间只能做一份兼职，请问小明每天最多可以做多少份的兼职？

面对这样的问题，其实在日常生活中，我们的第一选择肯定是先把结束时间早的兼职活动做了，然后再去做其他的兼职？这里面其实就是有贪心思想的应用，因为我们每次都是先做完结束时间早的兼职，然后我们会留出更多的时间可以做其他兼职。

这个问题里面的贪心选择就是每次选择最先结束的兼职活动，并且可以证明每次选择的最先结束的兼职活动是整体最优的，因为如果不是选择最先结束的兼职活动，剩下的可兼职的时间就少了，可以完成的兼职也就少了。同样，兼职选择活动具备最优子结构的性质，子问题可以选择的最多兼职在整体问题中同样适用。

场景 2：钱币找零问题

有 1 元、2 元、5 元、10 元的纸币分别有若干张，要用这些纸币凑出 m 元，至少要用多少张纸币？

这个是生活中最为常见的一种场景，经常我们在商场中用现金付款时，我们付出了 100 元，当收银员找零的时候，不知道大家有没有发现，收银员总是会先找零面额较大的货币，然后找零面额较小的货币，这个其实也是一个贪心选择的过程，因为这样可以保证找零的货币数量最少。

我们可以很明显的发现，贪心算法很多时候都是应用于求解一些最优化问题，与动态规划算法很相似，这类问题在现实生活或者学习科研中经常会遇到，这是一种解决问题的思路与方法，希望大家可以好好思考。

本节主要介绍了贪心算法的定义及基本概念，在学完本节课程之后，需要明白什么样的问题适合利用贪心算法求解，如何自己去设计一个贪心算法，以及我们日常生活中哪些应用场景适合用贪心算法思想求解。