第15章贪心法与动态规划法 随着程序设计中处理的数据量越来越大，对数据处理的高效率需求也越来越迫切，在 这一背景下，算法在程序设计中的作用显得尤其重要。贪心策略、动态规划等一系列运筹 学模型纷纷运用到程序设计中，产生了解决各种现实问题的有效算法。 贪心法（又称贪婪算法）是指：在对问题求解时，总是做出在当前看来是最好的选择 也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪心算 法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优 解或者是整体最优解的近似解。 将一个问题分解成为子问题求解，并且将中间子问题的结果保存起来以避免重复计算 的方法，就叫做“动态规划”。动态规划通常用来求最优解，能用动态规划求解的问题，必 须满足最优解的每个局部解也都是最优的。 15.1贪心法 贪心法是一种程序设计中常用的算法策略，在解决一些最优性问题时尤其具有简捷高 效的特点。 15.1.1贪心法的思想 在实际牛活中，经常会调到求一个问题的可行解和最优解的要求。这就是所谓的最优 化问题。每个最优化问题都包含一组限制条件和一个优化函数，符合限制条件的问题求解 方案称为可行解，使优化函数取得最佳值的可行解称为最优解。 贪心法是求解最优化问题的一种常用算法，它是从问题的某个初始解出发，采用逐步 构造最优解的方法向给定的目标推进。在每个局部阶段，都做出一个看上去最优的决策（即 某种意义下的、或某个标准下的局部最优解)，并期望通过每次所做的局部最优选择产生出 个全局最优解。做出贪心决策的依据称为贪心准则（策略），但要注意：决策一旦做出 就不可再更改。 贪心法是一种能够得到某种度量意义下的最优解的分级处理方法，通过一系列的选择 来得到一个问题的解，而它所做的每一次选择都是当前状态下某种意义的最好选择，即贪 心选择。每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题，以 数据处理中常见的选择排序为例，选择排序可以看做逐步确定目标有序序列每一个位置所 放元素的过程，每一步确定当前位置元素的过程就是一个求解局部区间最小值的子问题。 该问题的贪心选择过程可以简单描述为：第1步先获取有序序列第1个位置的元素， 即找出n个元素的最小值：第2步再获取有序序列第2个位置的元素，即找出剩余-l个 元素的最小值：：第n-1步获取有序序列第n-1个位置的元素，即找出剩余2个元素 的最小值：剩余1个数即为第n个位置的元素，即剩余1个元素的最小值。这样就把n个
第 15 章 贪心法与动态规划法 随着程序设计中处理的数据量越来越大，对数据处理的高效率需求也越来越迫切，在 这一背景下，算法在程序设计中的作用显得尤其重要。贪心策略、动态规划等一系列运筹 学模型纷纷运用到程序设计中，产生了解决各种现实问题的有效算法。 贪心法（又称贪婪算法）是指：在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪心算 法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优 解或者是整体最优解的近似解。 将一个问题分解成为子问题求解，并且将中间子问题的结果保存起来以避免重复计算 的方法，就叫做“动态规划”。动态规划通常用来求最优解，能用动态规划求解的问题，必 须满足最优解的每个局部解也都是最优的。 15.1 贪心法 贪心法是一种程序设计中常用的算法策略，在解决一些最优性问题时尤其具有简捷高 效的特点。 15.1.1 贪心法的思想 在实际生活中，经常会遇到求一个问题的可行解和最优解的要求，这就是所谓的最优 化问题。每个最优化问题都包含一组限制条件和一个优化函数，符合限制条件的问题求解 方案称为可行解，使优化函数取得最佳值的可行解称为最优解。 贪心法是求解最优化问题的一种常用算法，它是从问题的某个初始解出发，采用逐步 构造最优解的方法向给定的目标推进。在每个局部阶段，都做出一个看上去最优的决策（即 某种意义下的、或某个标准下的局部最优解），并期望通过每次所做的局部最优选择产生出 一个全局最优解。做出贪心决策的依据称为贪心准则（策略），但要注意：决策一旦做出， 就不可再更改。 贪心法是一种能够得到某种度量意义下的最优解的分级处理方法，通过一系列的选择 来得到一个问题的解，而它所做的每一次选择都是当前状态下某种意义的最好选择，即贪 心选择。每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题，以 数据处理中常见的选择排序为例，选择排序可以看做逐步确定目标有序序列每一个位置所 放元素的过程，每一步确定当前位置元素的过程就是一个求解局部区间最小值的子问题。 该问题的贪心选择过程可以简单描述为：第 1 步先获取有序序列第 1 个位置的元素， 即找出 n 个元素的最小值；第 2 步再获取有序序列第 2 个位置的元素，即找出剩余 n-1 个 元素的最小值；.；第 n-1 步获取有序序列第 n-1 个位置的元素，即找出剩余 2 个元素 的最小值；剩余 1 个数即为第 n 个位置的元素，即剩余 1 个元素的最小值。这样就把 n 个
数的排序问题（全局最优解）分解成次找当前序列中最小值（局部最优解）的子问题， 最后再把个局部最优解组合得到全局最优解。由此看来，贪心算法就是一种在每一步选 择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。 从上述简单排序的贪心求解过程，可以初步感受到一般贪心问题求解的基本思路框 架： (1)建立数学模型来描述问题。 (2)把求解的问题分成若干个子问题 (3)对每一子问题求解，得到子问题的局部最优解 (4)把子问颗的局部最优解合成原来问颗的一个解。 尽管通过局部最优解来获取全局最优解的贪心方法并非对所有问题都适合，但在求解 具有最优子结构和贪心选择性质的问题（比如：最短路径问题、最小生成树问题、哈夫曼 编码问题等)时却可以获得整体最优解。这类适合用贪心算法求解的问题常常具备一些相 同或相近的基本特征，比如：问题的数据结构（如：堆、最小树等）具备贪心的特性：或 者问题解决策略具有可证明的贪心特性：或者问题涉及博弈、游戏策略，这些策略大多是 贪心方法：或者问题需要求较优解或多次逼近最优解等。用贪心算法求解诸如此类的问题， 通常可以找到解决问题的最优算法，能够更加高效的完成问题求解任务。而且在这类可用 贪心法求解的问题中，用贪心算法一般比其它算法更加简单、直观和高效 15.1.2贪心法的实现过程 贪心法就是用局部解构造全局解，即从问题的某一个初始解逐步通近给定的目标，以 尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。 当确认问题可以用贪心法求解之后，贪心实现的基本过程可以分为以下三步： (1)从问题的某个初始解出发。 (2)Whi1e(能朝给定目标前进一步) 求出可行解的一个解元素 (3)由所有部分解组合成问题的 一个可行解 日常生活中大家身边也存在不少贪心的事例，这些事例通常都是采用上述贪心求解步 骤完成求解的。比如我们在超市购物时，经常需要从收银台找零钱，怎么提高收银台找零 钱的效率呢？这是一个典型的贪心问题。根据生活常识，收银员在为顾客找零钱时，为了 提高工作效率、减少顾客的等待时间，总是期望找给每个客户零钱所用的货币张数最少。 为此收银员不是一下给出所有零钱，而是采取逐步找零的贪心方法，即：收银员先给顾客 不超过待找零钱数额的面值最大的第一张零币，然后再给顾客不超过待找零钱余额的面值 最大的第二张零币，·，一直到所给零币总额满足项客待找零钱总额为止。 这样看来，解决找零钱问题的出发点 就是把该问题分成多个子问题，每个子问题的 目标是要找一张不超过当前要找钱数的最大面额的零币，其过程就是一个选择当前子问题 局部最优解的过程。当每个子问题的局部最优解都已经求得，综合以后就可以得到找零钱 张数最少的原问愿的可行解 比如收银员要找的钱为86元，现在的币值体系下，可以找的钱币面额分别为：50 元、20元、10元、5元、1元。首先找一个不超过86元的最大面额的货币，即50元，还 2
2 数的排序问题（全局最优解）分解成 n 次找当前序列中最小值（局部最优解）的子问题， 最后再把 n 个局部最优解组合得到全局最优解。由此看来，贪心算法就是一种在每一步选 择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。 从上述简单排序的贪心求解过程，可以初步感受到一般贪心问题求解的基本思路框 架： （1）建立数学模型来描述问题。 （2）把求解的问题分成若干个子问题。 （3）对每一子问题求解，得到子问题的局部最优解。 （4）把子问题的局部最优解合成原来问题的一个解。 尽管通过局部最优解来获取全局最优解的贪心方法并非对所有问题都适合，但在求解 具有最优子结构和贪心选择性质的问题（比如：最短路径问题、最小生成树问题、哈夫曼 编码问题等）时却可以获得整体最优解。这类适合用贪心算法求解的问题常常具备一些相 同或相近的基本特征，比如：问题的数据结构（如：堆、最小树等）具备贪心的特性；或 者问题解决策略具有可证明的贪心特性；或者问题涉及博弈、游戏策略，这些策略大多是 贪心方法；或者问题需要求较优解或多次逼近最优解等。用贪心算法求解诸如此类的问题， 通常可以找到解决问题的最优算法，能够更加高效的完成问题求解任务。而且在这类可用 贪心法求解的问题中，用贪心算法一般比其它算法更加简单、直观和高效。 15.1.2 贪心法的实现过程 贪心法就是用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以 尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。 当确认问题可以用贪心法求解之后，贪心实现的基本过程可以分为以下三步： （1）从问题的某个初始解出发。 （2）While（能朝给定目标前进一步） 求出可行解的一个解元素； （3）由所有部分解组合成问题的一个可行解。 日常生活中大家身边也存在不少贪心的事例，这些事例通常都是采用上述贪心求解步 骤完成求解的。比如我们在超市购物时，经常需要从收银台找零钱，怎么提高收银台找零 钱的效率呢？这是一个典型的贪心问题。根据生活常识，收银员在为顾客找零钱时，为了 提高工作效率、减少顾客的等待时间，总是期望找给每个客户零钱所用的货币张数最少。 为此收银员不是一下给出所有零钱，而是采取逐步找零的贪心方法，即：收银员先给顾客 不超过待找零钱数额的面值最大的第一张零币，然后再给顾客不超过待找零钱余额的面值 最大的第二张零币，.，一直到所给零币总额满足顾客待找零钱总额为止。 这样看来，解决找零钱问题的出发点，就是把该问题分成多个子问题，每个子问题的 目标是要找一张不超过当前要找钱数的最大面额的零币，其过程就是一个选择当前子问题 局部最优解的过程。当每个子问题的局部最优解都已经求得，综合以后就可以得到找零钱 张数最少的原问题的可行解。 比如收银员要找的零钱为 86 元，现在的币值体系下，可以找的钱币面额分别为：50 元、20 元、10 元、5 元、1 元。首先找一个不超过 86 元的最大面额的货币，即 50 元，还
需找86-50=36元：再找一个不超过36元的最大面额的货币20元，还需找36-20=16元： 再找 个不超过16元的货币10元，还需找16-10-6元：再找一个不超过6元的货币5元， 还需找6-5=1元：再找一个不超过1元的货币1元。这样共找出50元、20元、10元、5 元、1元的货币各1张，找零所用货币总张数为5，这是货币张数最少的找零方案。 找零问题的贪心实现过程如表15-1所示。 表15-1找零的贪心过程 当前欲 当前可找 本次贪 剩余待 当前解集合 找钱数 最大币值 心找家 找我数 36 40 2 36 20 20 16 {50,201 16 10 10 450.20.10月 4 6 {50.20.10.51 51 10 45020.10.5.1} 15.1.3贪心法的基本要素 贪心法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。其 实，读者从找零问题的贪心实现过程就可以感受到，贪心策略总是做出在当前看来是最优 的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上 的局部最优解。而众多问题之所以可用贪心法求解，是由于这些问题自身的特性决定了能 够将贪心策略获取的局部最优解组合得到全局最优解或较优解。这些特性主要包括以下两 点： (1)贪心选择性质： 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪 心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主 要区别。在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解 出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局 部最优选择。然后再去解做出这个选择后产生的相应的子间问题。贪心算法所做的贪心选择 可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。 正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常 以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求 问题简化为规模更小的子问题。 对于具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最 终导致问题的整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解， 使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后，用 数学归纳法证明，通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪 心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。 (2)最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用 3
3 需找 86-50=36 元；再找一个不超过 36 元的最大面额的货币 20 元，还需找 36-20=16 元； 再找一个不超过 16 元的货币 10 元，还需找 16-10=6 元；再找一个不超过 6 元的货币 5 元， 还需找 6-5=1 元；再找一个不超过 1 元的货币 1 元。这样共找出 50 元、20 元、10 元、5 元、1 元的货币各 1 张，找零所用货币总张数为 5，这是货币张数最少的找零方案。 找零问题的贪心实现过程如表 15-1 所示。 表 15-1 找零的贪心过程 步 骤 当前欲 找钱数 当前可找 最大币值 本次贪 心找零 剩余待 找钱数 当前解集合 1 86 50 50 36 {50} 2 36 20 20 16 {50,20} 3 16 10 10 6 {50,20,10} 4 6 5 5 1 {50,20,10,5} 5 1 1 1 0 {50,20,10,5,1} 15.1.3 贪心法的基本要素 贪心法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。其 实，读者从找零问题的贪心实现过程就可以感受到，贪心策略总是做出在当前看来是最优 的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上 的局部最优解。而众多问题之所以可用贪心法求解，是由于这些问题自身的特性决定了能 够将贪心策略获取的局部最优解组合得到全局最优解或较优解。这些特性主要包括以下两 点： （1）贪心选择性质： 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪 心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主 要区别。在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解 出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局 部最优选择。然后再去解做出这个选择后产生的相应的子问题。贪心算法所做的贪心选择 可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。 正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常 以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求 问题简化为规模更小的子问题。 对于具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最 终导致问题的整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解， 使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后，用 数学归纳法证明，通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪 心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。 （2）最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用
贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法 或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态 规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退：动态规划则会根 据以前的选择结果对当前进行选择，有回退功能。 15.1.4贪心法的注意事项 一个多阶段决策问题如果具备最优子结构性质，可以考虑用贪心法来求解。但并不是 具备最优子结构性质问题，就一定就能用贪心法求解。问题需要用贪心法求解时，应该验 证贪心的正确性以及选择合适的贪心策略。 (1)贪心的正确性 要证明贪心性质的正确性，是贪心算法的真正挑战，因为并不是每次局部最优解都会 与整体最优解之间有联系，有时靠贪心算法生成的解不是最优解。这样，贪心性质的证明 就成了贪心算法正确的关键。 对某些问题来讲，贪心方法在大部分数据中都是可行的，但还必须考虑到所有可能出 现的特殊情况，以保证该贪心性质在这些特殊情况中仍然正确，否则不经证明随便的使用 贪心算法可能就会得到错误的结果。 仍然以前面提到的找零问题为例，该问题虽然满足最优子结构性质，但并不意味着该 问题一定可以用贪心策略求解。只是由于现有的1、5、10、20、50}货币体系设计， 保障了该问题的贪心可以得到最优解。但是如果货币体系设计为{1、5、8、10}、要找的零 钱是13时，用前术含心方法所找出的零钱张数是4，面值分别为10、1、1和1，然而这里 的最优策略找出的零钱张数应该是2，面值为8和5。全局最优解并不包含局部最优解，在 这种情况下，贪心法失效了。 所以贪心法虽然执行效幸高，但适用范围却并不十分广泛，使用之前需证明贪心策略 是否能够得到问题的最优解。像上述找零一样的问题，如果货币体系设计不合理，贪心法 不能保证得到问题的最优解 就不适合用贪心了，这时我们可以用本章第3节介绍的动态 规划算法来实现问题求解。 (2)贪心策略的选择 对于可以用贪心算法求解的问题，当“贪心序列”中的每项互异且当问题没有重叠性 时，看起来总能通过贪心算法取得（近似）最优解的。但我们还需要选择合适的局部最优 策略，才能够保证求解结果的正确性，比如下面的背包问题： 问题描述：有一个容量M=200的背包，还有8种物品，每种物品的体积与价值如表 表15-28种物品的体积与价售 物品 GH 体积 40 5520 65 30 40 45 35 价值 35202040 35 15 4020 单位体积价值0.880.3610.621170380.890.57 15-2所示。假设每种物品可以取任意分量，现在要将物品装进背包，要求不能超过背 4
4 贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法 或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态 规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根 据以前的选择结果对当前进行选择，有回退功能。 15.1.4 贪心法的注意事项 一个多阶段决策问题如果具备最优子结构性质，可以考虑用贪心法来求解。但并不是 具备最优子结构性质问题，就一定就能用贪心法求解。问题需要用贪心法求解时，应该验 证贪心的正确性以及选择合适的贪心策略。 （1）贪心的正确性 要证明贪心性质的正确性，是贪心算法的真正挑战，因为并不是每次局部最优解都会 与整体最优解之间有联系，有时靠贪心算法生成的解不是最优解。这样，贪心性质的证明 就成了贪心算法正确的关键。 对某些问题来讲，贪心方法在大部分数据中都是可行的，但还必须考虑到所有可能出 现的特殊情况，以保证该贪心性质在这些特殊情况中仍然正确，否则不经证明随便的使用 贪心算法可能就会得到错误的结果。 仍然以前面提到的找零问题为例，该问题虽然满足最优子结构性质，但并不意味着该 问题一定可以用贪心策略求解。只是由于现有的{1、5、10、20、50.}货币体系设计， 保障了该问题的贪心可以得到最优解。但是如果货币体系设计为{1、5、8、10}、要找的零 钱是 13 时，用前述贪心方法所找出的零钱张数是 4，面值分别为 10、1、1 和 1，然而这里 的最优策略找出的零钱张数应该是 2，面值为 8 和 5。全局最优解并不包含局部最优解，在 这种情况下，贪心法失效了。 所以贪心法虽然执行效率高，但适用范围却并不十分广泛，使用之前需证明贪心策略 是否能够得到问题的最优解。像上述找零一样的问题，如果货币体系设计不合理，贪心法 不能保证得到问题的最优解，就不适合用贪心了，这时我们可以用本章第 3 节介绍的动态 规划算法来实现问题求解。 （2）贪心策略的选择 对于可以用贪心算法求解的问题，当“贪心序列”中的每项互异且当问题没有重叠性 时，看起来总能通过贪心算法取得（近似）最优解的。但我们还需要选择合适的局部最优 策略，才能够保证求解结果的正确性，比如下面的背包问题： 问题描述：有一个容量 M=200 的背包，还有 8 种物品，每种物品的体积与价值如表 表 15-2 8 种物品的体积与价值 物品 A B C D E F G H 体积 40 55 20 65 30 40 45 35 价值 35 20 20 40 35 15 40 20 单位体积价值 0.88 0.36 1 0.62 1.17 0.38 0.89 0.57 15-2 所示。假设每种物品可以取任意分量，现在要将物品装进背包，要求不能超过背
包总容量且物品总价值最大，该如何装包？ 要想总价值最大，可以试着用贪心法求解，通常大家容易想到以下的贪心策略： (1)每次取价值最大的物品： (2) 每次取体积最小的物品： (3)每次取单位体积价值最大的物品： 这三种贪心策略不同，按照这三种贪心策略进行求解，各自得到的装包方案是明显不 同，究竞哪一种是适合本问题的贪心策略呢？下面我们做一下比较。 采用第一种贪心策略，每次取价值最大的物品，贪心过程如表153所示 表15-3背包问题的贪心策略(1) 步背包当前 当前最大 本次盒心 所洗物品 己洗物品背包剩 当前解集合 可用容金 价值物品 选择物品 价值/体形 总价值 余容 1 200 D、G G 40/45 40 155 IG 2 155 4065 80 90 GD] 90 A、E 35/30 115 60 GDEI 3540 1s0 50 GDEA 5 20 B、C、H 20/20 170 0GD.E.A.C 采用第二种贪心策略，每次取体积最小的物品，贪心过程如表15-4所示： 表15-4背包问题的贪心策略(2) 步背包当前 当前最小 本次贪心所选物品己选物品背包剩 当前解集合 骤可用容量 体积物品 选择物品 价值/体积 总价值余容量 200 20/20 20 180 C 1g0 35/30 10 3 150 H 20/35 75 115 (C.E.H] 4 115 A、E A 35/40 110 75 CEHa 75 15/40 125 35 fC.EH.A.F) 6 35 G G 40/45156 0CE.H,A,F,G) 采用第三种贪心策略，每次取单位体积价值最大的物品，贪心过程如表15-5所示： 表15-5背包问题的贪心策略(3》 背句当 当前单位体本次贪心、所选物品 口洗物思 背句利 当前解集合 前容量 积最大价值 选择物品价值/体 总价值 余容量 200 E E 35/30 35 170 E 170 20/20 55 150 (EC) 3150 G G 40/45 95 115 EC.GI 4115 35/40 130 75 5 D 40/6 170 EC.GA.D 610 H H2035175.70E,C.GA.D,H田 比较一下三种贪心方案中背包里装下的物品的总价值，方案1为170，方案2为156 5
5 包总容量且物品总价值最大，该如何装包？ 要想总价值最大，可以试着用贪心法求解，通常大家容易想到以下的贪心策略： （1） 每次取价值最大的物品； （2） 每次取体积最小的物品； （3） 每次取单位体积价值最大的物品； 这三种贪心策略不同，按照这三种贪心策略进行求解，各自得到的装包方案是明显不 同，究竟哪一种是适合本问题的贪心策略呢？下面我们做一下比较。 采用第一种贪心策略，每次取价值最大的物品，贪心过程如表 15-3 所示； 表 15-3 背包问题的贪心策略（1） 步 骤 背包当前 可用容量 当前最大 价值物品 本次贪心 选择物品 所选物品 价值/体积 已选物品 总价值 背包剩 余容量 当前解集合 1 200 D、G G 40/45 40 155 {G} 2 155 D D 40/65 80 90 {G,D} 3 90 A、E E 35/30 115 60 {G,D,E} 4 60 A A 35/40 150 20 {G,D,E,A} 5 20 B、C、H C 20/20 170 0 {G,D,E,A,C} 采用第二种贪心策略，每次取体积最小的物品，贪心过程如表 15-4 所示； 表 15-4 背包问题的贪心策略（2） 步 骤 背包当前 可用容量 当前最小 体积物品 本次贪心 选择物品 所选物品 价值/体积 已选物品 总价值 背包剩 余容量 当前解集合 1 200 C C 20/20 20 180 {C} 2 180 E E 35/30 55 150 {C,E} 3 150 H H 20/35 75 115 {C,E,H} 4 115 A、F A 35/40 110 75 {C,E,H,A} 5 75 F F 15/40 125 35 {C,E,H,A,F} 6 35 G G 40/45 156 0 {C,E,H,A,F,G} 采用第三种贪心策略，每次取单位体积价值最大的物品，贪心过程如表 15-5 所示； 表 15-5 背包问题的贪心策略（3） 步 骤 背包当 前容量 当前单位体 积最大价值 本次贪心 选择物品 所选物品 价值/体积 已选物品 总价值 背包剩 余容量 当前解集合 1 200 E E 35/30 35 170 {E} 2 170 C C 20/20 55 150 {E,C} 3 150 G G 40/45 95 115 {E,C,G} 4 115 A A 35/40 130 75 {E,C,G,A} 5 75 D D 40/65 170 10 {E,C,G,A,D} 6 10 H H 20/35 175.7 0 {E,C,G,A,D,H} 比较一下三种贪心方案中背包里装下的物品的总价值，方案 1 为 170，方案 2 为 156