贪心法(I) 背包问题
++++++++++++++++++++++++++++++++++

背包问题是一类非常经典的算法问题，它是要把 :math:`n` 种不同物品有选择地放进一个背包中，物品有各自的重量 :math:`\{w_1,w_2,\dots,w_n\}` 和价值 :math:`\{v_1,v_2,\dots,v_n\}`\ ，背包有最大承重限制 :math:`W`\ ，我们要选择一个最优的物品组合放入背包中，使得背包中物品的总价值 :math:`V` 最大化。通常这些重量和价值都采用正整数来表示。

常见的背包问题有\ :strong:`部分背包问题`\ 、:strong:`0-1背包问题`\ 、:strong:`完全背包问题`\ 和\ :strong:`多重背包问题`\ ，其中前两种是最常见的。这里面只有部分背包问题是贪心法可解的。其他三种都不适用贪心法，尽管它们都有一种可行的伪多项式时间算法，但实际上它们都是NP难题。下面我们分别对部分背包问题的贪心算法和0-1背包问题的贪心法不可解性质进行介绍。至于0-1背包等其他三种背包问题的伪多项式时间算法，是必学、常考的经典动态规划算法，我们将在讲述动态规划的章节中进行介绍。


部分背包问题
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

在部分背包问题中，所有的物品都是可以拆分的，最小可以拆到重量为1。部分背包问题的另一种常见形式是不同浓度的溶液混合，使混合后的溶液浓度最大化。

部分背包问题是可以用贪心法求解的，但是要正确选择贪心策略。对于背包问题，选择物品的策略有三种：一是依据重量选择，重量越小的越优先；二是依据价值选择，价值越大的越优先；三是依据单位重量的价值选择，单位重量的价值越大的越优先。

按照生活经验，直观地就会选择第三种贪心策略，按单位价值进行从大到小的选择（似乎用混合溶液的提法更容易直观理解）。那么如何用精准的数学语言来证明它呢？这个证明要利用到部分背包问题的一个特殊性质，背包总是能够被塞满，因此最终放入背包的物品的重量总和恒等于 :math:`W`\ 。为了证明这个贪心策略是能够得出正确的最优解的，我们首先要看一下怎么应用它。

首先计算出每一种物品的单位价值 :math:`\rho_i=v_i/w_i`\ ，然后对它们进行排序，得到一个有序的序列 :math:`\rho_{i_1}\le\rho_{i_2}\le\dots\le\rho_{i_n}`\ 。这里的 :math:`\{i_1,i_2,\dots,i_n\}` 是物品编号 :math:`\{1,2,\dots,n\}` 的一个排列。

例如我们的背包总承重限制为 :math:`W=6`\ ，共有四种物品，它们的编号、重量、价值和计算得到的单位价值（保留1位小数）如下表：

+-------------------+-----------------+-----------------+------------------------+
| 物品编号 :math:`i`| 重量 :math:`w_i`| 价值 :math:`v_i`| 单位价值 :math:`\rho_i`|
+===================+=================+=================+========================+
|         1         |        3        |        7        |           2.3          |
+-------------------+-----------------+-----------------+------------------------+
|         2         |        2        |        2        |           1.0          |
+-------------------+-----------------+-----------------+------------------------+
|         3         |        4        |        8        |           2.0          |
+-------------------+-----------------+-----------------+------------------------+
|         4         |        5        |        9        |           1.8          |
+-------------------+-----------------+-----------------+------------------------+

于是我们可以得到一个依单位价值从小到大的物品排列 :math:`\{2,4,3,1\}`\ 。

下一步就是应用单位价值大者优先的贪心策略来选取放入背包的物品。从具有最大单位价值 :math:`\rho_{i_n}` 的物品 :math:`i_n` 开始，逐个从后向前选取物品，如果背包剩余的可装重量不足以全部装下当前选择的物品了，那么就从该物品中拆分出恰好等于背包剩余承重的部分来塞满整个背包。如此进行贪心选择，最终得到的解 :math:`\{i_n,i_{n-1},\dots,i_k\},(1 \le k \le n)` 就是最优解。此解中的物品重量总和一定为 :math:`W`\ ，其中物品 :math:`i_n,i_{n-1},\dots,i_{k+1}` 全部装入背包，最后一项物品 :math:`i_k` 装入背包的重量为 :math:`w^\prime_{i_k}\le w_{i_k}`\ ，所以可以计算出这个解得到的背包中物品总价值为 :math:`V=v_{i_n}+v_{i_{n-1}}+\cdots+v_{i_{k+1}}+w^\prime_{i_k}\times\rho_{i_k}`\ 。

例如在我们上面这个例子中，按照这个策略来取物品，得到的解依次包含物品 :math:`\{1,3\}`\ ，其中物品 :math:`3` 所取的重量为 :math:`3`\ ，所以解的总价值为 :math:`7+3\times2.0=13.0`\ 。

这个贪心解一定是最优解吗？答案是肯定的。我们可以这样想，根据这个策略得到的解，包里所装的物品有 :math:`\{i_n,i_{n-1},\dots,i_k\}`\ ，未装入包里的物品有 :math:`\{i_k,i_{k-1},\dots,i_1\}`\ 。因为物品编号的排列 :math:`\{i_1,i_2,\dots,i_n\}` 满足单位价值有序：:math:`\rho_{i_1}\le\rho_{i_2}\le\dots\le\rho_{i_n}`\ ，所以任何一种未装入背包的物品的单位价值都不会高于任何一种已装入背包的物品的单位价值，故对任意 :math:`1\le p\le k` 和 :math:`k\le q\le n`\ ，都保证 :math:`\rho_{i_p}\le\rho_{i_q}` 恒成立。而部分背包问题的特性使得我们总要保持解中所有物品的总重量之和恒为背包总承重量 :math:`W` 不变，使得如果要对解进行变动，必然是要用未放入背包的物品去等重量地替换已经放入背包里的物品。假使我们使用任意重量 :math:`w` 的任意未放入背包的物品 :math:`i_p`\ ，用它来替换等重的已放入背包物品 :math:`i_q`\ ，那么从解中换出去的价值 :math:`w\cdot\rho_{i_q}` 必然不会小于换进来的价值 :math:`w\cdot\rho_{i_p}`\ ，所以这样的交换必然得不偿失，不可能使解的总价值得到提升，只可能下降。

到此就证明了我们得到的贪心解，是已经不可能通过任何交换来使其价值更大了，它就是最优解。有兴趣的可以用我们上面的示例数据来试一试，看看能不能找出总价值比13.0更大的解来。

.. admonition:: 练习

   部分背包问题的贪心算法就讲解完了，但是你能编出这样一个程序来吗？事实上要编出这个程序来还是有一定难度的，请尝试一下。

.. hint::

   要编写这个程序，第一个要注意的地方是单位价值不一定是整数，但是考虑到浮点数的精度问题，最好不要用浮点数进行排序，那么就需要将小数比大小改成分数比大小，怎么办？第二个要注意的地方是对单位价值进行排序的时候不能丢失原有的物品编号，也就是说要带着物品编号排序。

   请认真回顾排序的相关章节，解决上述两个问题，那么编写出部分背包问题的算法程序也就非常简单了。


0-1背包问题初探
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

0-1背包问题是最为经典的背包问题。所谓“0-1”的意思就是指物品不能拆分且每种物品只有一件，要么不放入背包，要么放入背包，非0即1。其他规则和目标与部分背包问题全无二致。

现在有一个坏消息和一个好消息。坏消息是：:strong:`0-1背包问题是NP难题`\ ；好消息是：:strong:`它有一个很好用的` :math:`O(nW)` :strong:`时间的动态规划解法`\ ，其中 :math:`W` 是背包总承重，:math:`n` 是物品种数。

我们在这里不打算详细介绍0-1背包问题的动态规划解法，这个算法留到后面动态规划的部分再讲。现在我们只是来初窥一下这个NP难题，看看为什么贪心法对它不起作用。

通过前面几个简单的例子已经可以看出来，想知道一个问题能不能用贪心法，贪心策略靠不靠谱，往往首先是来自于经验和直觉。但是也会有一些问题，会让人迷惑，对自己的经验和直觉没那么有信心。这种时候有两个选择，一是设法去证明贪心策略正确，二是设法去证伪。而证伪往往比证明简单得多，只要你能找到一个反例，证伪就成功了。证明则需要严密的数学和逻辑推理。从前面两个例子也可以看出，要严格证明一个最简单的贪心策略都可能不是那么简单的。

0-1背包问题的证伪就很简单，我们前面举的那个示例就是一个非常好的反例素材，让我们再来看一看它的数据：背包总承重限制为 :math:`W=6`\ ，共有四种物品，它们的编号、重量、价值和计算得到的单位价值（保留1位小数）如下：

+-------------------+-----------------+-----------------+------------------------+
| 物品编号 :math:`i`| 重量 :math:`w_i`| 价值 :math:`v_i`| 单位价值 :math:`\rho_i`|
+===================+=================+=================+========================+
|         1         |        3        |        7        |           2.3          |
+-------------------+-----------------+-----------------+------------------------+
|         2         |        2        |        2        |           1.0          |
+-------------------+-----------------+-----------------+------------------------+
|         3         |        4        |        8        |           2.0          |
+-------------------+-----------------+-----------------+------------------------+
|         4         |        5        |        9        |           1.8          |
+-------------------+-----------------+-----------------+------------------------+

接下来逐一尝试一下三种贪心策略：

1. 重量轻者优先：放入背包的物品依次将是 :math:`2` 号和 :math:`1` 号，总重量 :math:`2+3=5`\ ，产生的总价值为 :math:`2+7=9`\ ；
2. 价值大者优先：放入背包的物品将只有 :math:`4` 号，重量 :math:`5`\ ，产生的总价值为 :math:`9`\ ；
3. 单位价值高者优先：这次放入背包的物品依次为 :math:`1` 号和 :math:`2` 号，因为放入物品 :math:`1` 后剩余背包容量减少为 :math:`3`\ ，单位价值第二高的物品 :math:`3` 已经放不下了，因此跳过，接下来还可以放下物品 :math:`2`\ ，然后就再也放不下任何别的物品了，总重量为 :math:`3+2=5`\ ，总价值为 :math:`7+2=9`\ 。

但是，这么简单的数据用人脑一看就可以发现，选择物品 :math:`2` 和物品 :math:`3` 可以得到更大的价值，二者重量总和为 :math:`2+4=6`\ ，恰好塞满背包，总价值为 :math:`2+8=10`\ ，比所有三种贪心算法得到的解都更优！

问题就出在0-1背包问题不能拆分物品，所以无论用什么贪心策略，都有可能使背包没有完全塞满，或者还塞得不够满。而真正的最优解有可能比它们更加能充分利用背包的承重量，把限制条件用得更彻底。这种如何合理摆布从而使得约束条件被充分利用的思路是一种整体思路，需要通盘考虑多个因素。很不巧，贪心法却是一种“只看眼前利益”的方法，它天生目光短浅，没有通盘考虑的能力。