贪心法
======

:strong:`贪心法`\ 指的是求解最优化问题的一种方法，它不从整体最优上考虑如何解决问题，而是把求解过程分为多个相对简单的子过程或步骤，每一步都总是做出\ :strong:`当下最好`\ 的选择，即求出所谓\ :strong:`局部最优解`\ ，最后通过这些局部最优解来得到整体的\ :strong:`全局最优解`\ 。

.. hint::

   贪心法是动态规划的一种特例。能用贪心解决的问题，也可以用动态规划解决。


贪心法使用的分解求解过程的方法叫做\ :strong:`贪心策略`\ 。如果使用的贪心策略具有最优子结构的特点，也就是说它具备\ :strong:`无后效性`\ ，即每一步局部最优解的求解都只和问题的当前状态有关，而不会受到后续求解过程的影响，那么最终就可以得到全局最优解。如果所使用的贪心策略具有后效性，那么算法就可能得不到最优解，而只能得到一个近似最优的解。

.. warning::

   贪心法不保证一定能获得最优解！


所以对所采用的贪心策略一定要仔细分析其是否满足无后效性，换句话说，一定要证明其正确性。但这不是一件容易的事情，并没有一种固定的证明方法，需要具体问题具体分析。而且实际上，:strong:`适用贪心法的情况很少`\ 。一般来说，要分析一个问题是否适用贪心法，一靠经验、二靠尝试举反例、三才是形式化的证明。

**单机任务调度问题**

单机任务调度问题是\ :strong:`任务调度问题`\ 中最简单的一类，是典型的贪心算法用例。假设有 :math:`n` 项任务 :math:`\{1,2,\dots,n\}` 提交到一台机器上运行，机器只能逐个顺序运行这些任务，不能同时运行多个任务。给出这 :math:`n` 项任务各自的运行时长 :math:`\{t_1,t_2,\dots,t_n\}`\ ，按要求给出这些任务先后运行顺序的一个最优调度。这个问题通常会有两种问法，一是机器一次开机最多连续运行 :math:`m` 时长，要求一个最优调度，使得在这个时间限制之内能完成的任务个数最多；二是从0时刻开始计时，直到全部任务运行完成，每个任务完成的时间累加起来得到任务完成的总时间，要求给出一个最优调度，使得所有任务完成的总时间最短（有时候也会说是任务平均等待时间最短）。

上述这两类单机调度问题，本质上是一样的，因此可以用同一个贪心算法正确地予以解决。这里用的贪心策略非常直观，就是先易后难的原则，每次都先调度运行时间最短的那个任务即可。具体来说，读入所有 :math:`n` 个任务的运行时长后，对它们进行一个从小到大的排序，然后按这个顺序进行调度就可以了。两个提问不同之处仅在于，对于第一种提问我们只需要调度到限制时间 :math:`m` 用光，不够运行下一个任务就结束了，对于第二种提问则把排好序的任务依次调度完即可。

例如一共有5个任务，完成时间各自为 :math:`t_1=3,t_2=8,t_3=5,t_4=15,t_5=10`\ ，那么排序后的顺序为 :math:`\{t_1,t_3,t_2,t_5,t_4\}`\ 。

如果机器的运行时限为20，那么能完成最多任务的调度就是 :math:`\{1,3,2\}`\ ，共计能完成3项任务，总耗时 :math:`3+5+8=16`\ ，剩余时间 :math:`20-16=4\lt t_5=10`\ ，已经不能再继续运行第5号任务了，调度结束。

如果没有限制机器运行时间，而是要求所有任务的完成时间之总和最小，依然是按照这个顺序，把所有任务调度完即可，这个调度就是 :math:`\{1,3,2,5,4\}`\ 。按照这个调度，任务运行总时间为：

.. math::

   \begin{align}
   T=&(t_1)+(t_1+t_3)+(t_1+t_3+t_2)+(t_1+t_3+t_2+t_5)+(t_1+t_3+t_2+t_5+t_4)\\
    =&5\times t_1+4\times t_3+3\times t_2+2\times t_5+1\times t_4\\
    =&5\times3+4\times5+3\times8+2\times10+1\times15\\
    =&94
   \end{align}

这是所有任务完成时间之和的最小值。要证明这个结论也很简单，因为排在前面的任务在计算总时间的时候它的运行时长被加的次数总是比排在后面的任务多。假设在调度中存在一个逆序对 :math:`t_i\gt t_{i+1}`\ ，那么 :math:`t_i` 会在计算总时间时被加 :math:`n-i+1` 次，:math:`t_{i+1}` 则会被加 :math:`n-i` 次，因此这个逆序对给总时长带来的时间量是 :math:`(n-i+1)t_i+(n-i)t_{i+1}=(n-i)\cdot(t_i+t_{i+1})+t_i`\ 。而如果把这个逆序对转成顺序对，那么它们给总时长带来的时间量会是 :math:`(n-i)\cdot(t_i+t_{i+1})+t_{i+1}`\ 。显然，由于 :math:`t_i\gt t_{i+1}`\ ，所以逆序对带来的时间量一定比顺序对带来的时间量要长。按照我们的贪心策略得到的调度，是完全不存在逆序对的，所以这个调度一定是最优的。

上面是一个最简单的贪心法的例子，也很好理解。尽管贪心法的实际应用场景并不多，但它是一种重要的算法设计思路，在初期的算法竞赛中是常考题型，在一些高级算法中也常会存在部分采用贪心法的情况。另外，贪心法还常会作为一种比较简单实用的较优解近似算法用于某些NP难题。因此对贪心法做一个比较全面的了解，包括它的常见用例、常见反例和一些实际考题是很有必要的。下面就让我们来看一些经典的贪心法例子，最后用两个实际题目来巩固一下贪心法的应用。

.. toctree::
   :maxdepth: 2

   sec01/411_greedy_bag_problems
   sec01/412_greedy_complex_scheduling
   sec01/413_greedy_integer