对于AI产品经理来说，掌握一些算法是必要的。本文将从五个方面，讲述AI产品经理必修的贪心算法，希望对你有帮助。

去年“新智元”有一篇报道《清华毕业计算机教授遭持枪劫车，靠“贪心算法”追回秒杀美国警察》，整个故事像看微小说一样，可对于核心问题“贪心算法”是什么并没有说清楚，于是就有了下面的内容。

一、什么是贪心算法

贪心的意思在于在作出选择时，每次都要选择对自身最为有利的结果，保证自身利益的**化，贪心算法就是利用这种贪心思想而得出一种算法。

贪心算法可以简单描述为：大事化小，小事化了。对于一个较大的问题，通过找到与子问题的重叠，把复杂的问题划分为多个小问题。并且对于每个子问题的解进行选择，找出**值，进行处理，再找出**值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下**或**的选择，从而希望得到结果是**或**的算法。

贪心算法在对问题求解时，总是做出在当前看来是**的选择。也就是说，不从整体**上加以考虑，所做出的仅是在某种意义上的局部**解。贪心算法不是对所有问题都能得到整体**解，但对范围相当广泛的许多问题他能产生整体**解或者是整体**解的近似解。

二、贪心算法基本思路

步骤一：建立数学模型来描述问题。

步骤二：把求解的问题分成若干个子问题。

步骤三：对每个子问题求解，得到子问题的局部**解。

步骤四：把子问题的解局部**解合成原来问题的一个解。

三、贪心算法的选择

所谓贪心选择是指所求问题的整体**解可以通过一系列局部**的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。

贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体**解。

我们下面通过示例来看一下贪心算法如何选择。

四、贪心算法示例

看一下《算法导论》中的经典例题：活动选择问题。

有n个需要在同一天使用同一个教室的活动a1，a2……an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行（标红的是我们利用贪心算法求出的结果1、4、8、11）。