1. 基本定义
虽然使用动态规划算法可以得到全局最优解，但当问题的规模很大的时候，我们并不想花费很多内存空间及计算资源去维护一个特征转移矩阵。为了节省资源，是否可以直接去掉转移矩阵，直接认为上一个时刻的解就是最优解，并且，可以基于上一个时刻得到当前时刻的最优解？于是，就有了贪心算法（Greedy Algorithm）。
贪心算法可以说是动态规划的精简版，或者说是有条件的动态规划。贪心算法得到的是局部最优解（所以这是贪心的），而非全局最优解。所以，贪心算法适用场景，动态规划也一定可以适用，但动态规划适用的场景，贪心算法就不一定适用。
贪心算法在现实中应用广泛，因为很多时候，贪心算法可以节省掉很多资源，而这代价仅仅为只能得到一个十分接近最优解的答案。在对结果要求不严格的情况下，这个交易是相当划算的。
但在解题的时候，贪心算法一般不是首先需要考虑的算法，除非是有运行时间或内存空间的限制，并且可以证明贪心算法给出的结果就是全局最优解。
2. 设计步骤
- 将原问题转化为：对其作出一次选择后，只剩下一个子问题需要求解。
- 证明作出贪心选择后，原问题总存在最优解，即贪心选择总是安全的（一般使用反证法证明）。（这也就意味着贪心算法一般都伴随着排序操作）
- 证明作出贪心选择后，剩余的子问题满足性质：最优解和贪心选择组合即可得到原问题的最优解。
3. 一些例子
贪心算法没有固定的套路，全靠悟性！！！
至于什么时候应动态规划，什么时候用贪心，暂时没找到很好的办法去区分，能用贪心的，用dp一定可以做出来，所以先用dp做一遍，如果确定算法没有错，但提示超时了，那一定就有贪心策略。
还有通过贪心算法的本质，我们也可以得出以下规律：
- 贪心算法不能解决达到目的的方法总数之类的问题
- 贪心算法的实现一般基于循环。
3.1. 部分背包
问题描述
已知有\(n\)个物品，第 \(i\) 物品的重量为 \(w_i\)，价值为 \(v_i\)，背包的最大可装载的重量为 \(W\)，所有物品可以部分装进背包，重量和价值成正比，问：怎样装可使价值最大化。
问题分析
这是一道经典的贪心算法例题（特别地，这道题如果使用dp求解，会变得非常麻烦）。
回到这道题目，首先，怎样才能使价值最大化。这里，由于没了物品只能整个装进背包的桎梏，所以，理所当然地我们应当想到，首先把性价比（\(p_i = v_i/w_i\)）高的装进背包，背包的总价值自然较高。所以我们按性价比对物品排序，按该顺序装填物品，直到背包已满。
验证贪心算法的安全性。
是否存在其他装载的方法使得最终的总价值更高？
假设这是一个按性价比排序的物品序列 \(x_0, x_1, \cdots,x_n\)，按照贪心算法的假设，必然有 \(p_{x_1} < p_{x_0}\) 。现在，我们使用还没装填的第 \(x_1\) 件物品代替已经装填的第 \(x_0\) 件物品。于是，我们有以下两种情况：
装填部分的重量 \(w_{x_0} \geq w_{x_1}\) 。替代前价值为 \(v_0=p_{x_0} w_{x_0}\)，替代后的价值为 \(v_1 = p_{x_1} w_{x_1} + p_{x_2} (w_{x_0}-w_{x_1})\) ，其中，\(x_2\) 是用来填补缺少部分的物品下标。计算可得 \(v_0 - v_1=(p_{x_0} - p_{x_2})w_{x_0} + (p_{x_2} - p_{x_1})w_{x_1}\)，由于 \(|p_{x_0} - p_{x_2}| >|p_{x_2} - p_{x_1}|,p_{x_0} - p_{x_2}\geq0,p_{x_2} - p_{x_1}\leq 0,w_{x_0} \geq w_{x_1}\)，故 \(v_0 > v_1\)；
反之，装填部分的重量 \(w_{x_0} < w_{x_1}\) 。我们也能如法炮制地得到\(v_0 > v_1\)，这里就不赘述了。
综上，按贪心算法得到的总价值是最高。
所以，我们首先计算出每个物品的性价比，然后按性价比从高到低的顺序往背包里面塞物品，直到背包已满。
这道题经常用来和0-1背包进行对比。0-1背包问题不能使用贪心算法，因为按照贪心算法，背包可能会剩余空间，这些空间不能再装下任意一件物品，但这些剩余空间是存在价值的，贪心算法却将其丢弃了，所得的解自然不是全局最优解。
编程实现
def greedy(n, W, w, v): p = [(i, v[i] / w[i]) for i in range(n)] p = sorted(p, reverse=True, key=lambda x: x[1]) r = 0 for i, pi in p: if W > w[i]: r += v[i] else: r += pi * W break W -= w[i] return r程序验证
>>> W = 9 >>> w = [2, 3, 5, 7] >>> v = [1, 5, 2, 4] >>> n = len(w) >>> greedy(n, W, w, v) 8.428571428571429
3.2. 跳跃问题
问题描述
已知在 \(i\) 米处，你最大可以跳跃 \(a_i(a_i>0)\) 米，路径全长 \(n\) 米，问：从起点跳到终点最少跳跃多少次。
问题分析
设当前处于 \(i_0\) 米，最大可以跳跃到 \(m_0=i_0+a_{i_0}\) 米处，
那么我们只需要在区间 \((i_0,m_0]\) 中（如果是dp，还需考虑区间 \([0,i_0]\)）找到一个点，使其满足 \(m_1 = \max \{ i_k+a_{i_k}|i_0<k \leq m_0\}\)
然后令 \(i_0=m_0,m_0=m_1\)，重复上述操作，直到 \(m_1 \geq n\)
验证贪心选择的安全性。
首先，从 \(i_0\) 到 \(m_1\) 至少需要跳跃2次，那么可以只需要跳1次吗？
假设其可以，则 \(i_0\) 最大可以跳跃到 \(m_1\) 处，这明显跟原贪心算法的假设相悖，故该假设不成立。
其次，那可以通过跳跃两次，从 \(i_0\) 到 \(m_2(m_2>m_1)\) 吗？
假设其可以，因为第一次跳跃最大只能跳到 \(m_0\) 处，所以要想跳到 \(m_2\) 处，只能靠第二次跳跃，但第二次跳跃最大也只能到 \(m_1\) 处。所以该假设不成立。
所以该问题下，贪心算法是work的。
特别地，这道题如果使用dp求解，空间复杂度为 \(O(n^2)\)，时间复杂度为 \(O(n^2)\)，而使用贪心算法求解，空间复杂度为 \(O(1)\)，时间复杂度为 \(O(n)\)
编程实现
def greedy(A): n = len(A) m0, m1, steps = 0, 0, 0 for i in range(n - 1): m1 = max(A[i] + i, m1) if m0 == i: steps += 1 m0 = m1 return steps程序验证
>>> A = [2, 3, 1, 1, 4] >>> greedy(A) 2
3.3. 无重叠区间
问题描述
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
问题分析
要使移除区间的数量最小，则应该尽可能多地保留密集的区间且尽可能多地移除跨度较大区间。
为此，我们需要先对所有区间的终点（不选择起点的原因是无法保证贪心选择的安全性，后面也会谈到这一点）从小到大进行排序遍历。设第 \(i\) 个区间为 \([s_0,e_0]\)，继续往下遍历，设第 \(i+1\) 个区间为 \([s_1,e_1]\)，如果 \(s_1<e_0\)，说明这两个区间重叠，则移除第 \(i+1\) 个区间。重复上面的遍历操作，直到遍历到第 \(i+j\) 个区间 \([s_{i+j},e_{i+j}]\)，有 \(s_{i+j}>e_0\)，则说明两个区间没有重叠，另 \(e_0=e_{i+j}\)，继续上面操作。
最终移除的区间就是移除区间的最小数量。
验证贪心选择的安全性。
假设按贪心算法操作，从第 \(i\) 个到第 \(i+j\) 个区间中移除的区间数量为 \(x\)，那是否存在其他办法，让从第 \(i\) 个到第 \(i+j\) 个区间中移除的区间数量为 \(y\)，使得 \(x>y\) 呢？
假设 \(y\) 存在。
我们从排序后的区间序列中选取两段相邻的区间 \([i_0,i_1]\) 和 \([i_2, i_3]\)，设这两个区间重叠区间数大于0且分别为 \(x_0\) 和 \(x_1\)，对此，我们总能找到一个开始坐标离 \(i_0\) 最近的区间 \([j_0,j_1]\)，特别地，\(x_0\) 不包含 \([i_0,j_0]\) 区间内的重叠数，因为这个区间内的重叠数已经被计算过一遍了。
设 \([j_0,i_1]\) 和 \([i_1,j_1]\) 两个区间的重叠数分别为 \(y_0\) 和 \(y_1\) ，\([i_0,j_1]\) 的重叠总数为 \(x\)，\([j_0,j_1]\) 的重叠总数为 \(y\)。其中，我们容易得到 \(x_0=y_0\)；然后， \(j_1\) 只有两种状态：
当 \(i_1 \leq j_1 \leq i_2\) 时，因为 \([i_1,j_2]\) 不存在独立的区间，故 \([i_0,j_1]\) 和 \([j_0,j_1]\) 的重叠总数相等，即 \(x=x_0=y_0=y\)；
当 \(i_2 < j_1 \leq i_3\) 时，我们也可得到 \([i_2,j_1]\) 和 \([i_1, j_1]\) 的重叠数是相等的，我们有 \(x=x_0+k_0,y=y_0+k_1\)，其中，\(k_0\) 为只与 \([i_2,j_1]\) 重叠而不与 \([i_0,i_1]\) 重叠的区间数，\(k_1\) 为只与 \([i_1, j_1]\) 重叠而不与 \([i_0,i_1]\) 重叠的区间数。明显我们能得到 \(k_0=k_1+1\)，故 \(x<y\)
综合两种情况（其实画个图就会一目了然），在 \([i_0,j_1]\) 区间内，我们始终可以得到 \(x \leq y\)。继而，推广至 \([i_2, i_3]\) 和 \([i_4,i_5]\) 区间的情况，我们仍能得到上面的结论，任意区间都有 \(x \leq y\) ，故 \(y\) 不存在。所以该问题下，贪心算法是work的。
贪心算法的空间复杂度为 \(O(1)\)，时间复杂度为 \(O(n \log n)\)
编程实现
def greedy(a): a = sorted(a, key=lambda x: x[1]) x = 0 e = a[0][1] for i in range(1, len(a)): if a[i][0] < e: x += 1 continue e = a[i][1] return x程序验证
>>> a = [[1, 2], [2, 3], [3, 4], [1, 3]] >>> greedy(a) 1
What a nice day~
