《程序设计基础》课程教学资源（教材讲义）5、贪心与动归.pdf_大学文库

第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 所示。假设每种物品可以取任意分量，现在要将物品装进背包，要求不能超过背

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

方案3为175.7。这里只有第3种策略得到的才是符合要求的最优解。 15.2贪心法实例 15.2.1删数问题【例15.1】删数问题。键盘输入一个高精度的正整数n(≤100位)，去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的与s,寻找一种方案，使得剩下的数字组成的新数最小。比如：n=178543,s=4 则输出13，表示正整数178543，删除4位数字后得到的最小值是13。分析： (1)由于给定的正整数有效位数是100位，用一般的整数类型（包括长整数）无法表示，可以考虑用字符串来存储正整数。 (2)如何决定哪s位数字被删除呢？被删除的是否是最大的s个数字呢？为了尽可能逼近目标，我们采用贪心法来解决问题，选取的贪心策略为： ①把对s个数字的删除，看成是一个逐步实现的过程，每一步删除一个数字，用s步完成对s个数字的删除。 ②每一步总是选择一个使剩下的数最小的数字完成删除，也就是按照从高位到低位的顺序进行搜索，如果各位数字是递增的，则刷除最后一位数字：否则，删除第一个递减区间的首位数字。这样选择一位数字并删除后，便得到一个新的数字串 ③以后每一步回到上一步完成删除之后的数字串的串首，按照上述规则再别除下一个数字。执行s次后，便删除了s位数字，剩余的数字串便是问题的解。例如：n=178543,s-4时的删除过程为：第一步：n=178543,第一个递减区间为8543，删除其首位数字8。第二步：=17543，第一个递减区间为7543，删除其首位数字7。第三步：n=1543,第一个递减区间为543，删除其首位数字5 第四步：=143，第一个递减区间为43，别除其首位数字4。剩余的数字串为：13，即为所求。该问题求解的具体贪心策略如表15-6所示。表15-6删数问题的贪心策略步骤当前数字串第一个递减区间递减区间首位数字剩余数字串当前解集合 1 178543 8543 17543 {8 2 17543 7543 7 1543 871 1543 543 143 8.7.51 143 43 13 8.7.5.4} 根据上述思路，可以得到如下的程序： 6

6 方案 3 为 175.7。这里只有第 3 种策略得到的才是符合要求的最优解。 15.2 贪心法实例 15.2.1 删数问题【例 15.1】删数问题。键盘输入一个高精度的正整数 n（≤100 位），去掉其中任意 s 个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的 n 与 s，寻找一种方案，使得剩下的数字组成的新数最小。比如：n=178543，s=4 则输出 13，表示正整数 178543，删除 4 位数字后得到的最小值是 13。分析：（1）由于给定的正整数有效位数是 100 位，用一般的整数类型（包括长整数）无法表示，可以考虑用字符串来存储正整数。（2）如何决定哪 s 位数字被删除呢？被删除的是否是最大的 s 个数字呢？为了尽可能逼近目标，我们采用贪心法来解决问题，选取的贪心策略为： ① 把对 s 个数字的删除，看成是一个逐步实现的过程，每一步删除一个数字，用 s 步完成对 s 个数字的删除。 ② 每一步总是选择一个使剩下的数最小的数字完成删除，也就是按照从高位到低位的顺序进行搜索，如果各位数字是递增的，则删除最后一位数字；否则，删除第一个递减区间的首位数字。这样选择一位数字并删除后，便得到一个新的数字串。 ③ 以后每一步回到上一步完成删除之后的数字串的串首，按照上述规则再删除下一个数字。执行 s 次后，便删除了 s 位数字，剩余的数字串便是问题的解。例如：n=178543，s=4 时的删除过程为：第一步：n=178543，第一个递减区间为 8543，删除其首位数字 8。第二步：n=17543，第一个递减区间为 7543，删除其首位数字 7。第三步：n=1543，第一个递减区间为 543，删除其首位数字 5。第四步：n=143，第一个递减区间为 43，删除其首位数字 4。剩余的数字串为：13，即为所求。该问题求解的具体贪心策略如表 15-6 所示。表 15-6 删数问题的贪心策略步骤当前数字串第一个递减区间递减区间首位数字剩余数字串当前解集合 1 178543 8543 8 17543 {8} 2 17543 7543 7 1543 {8,7} 3 1543 543 5 143 {8,7,5} 4 143 43 4 13 {8,7,5,4} 根据上述思路，可以得到如下的程序：