f(Program,Poet)=Programet

4.贪心方法
a.工程计划模型
b.部分背包与每步最优
c.构造贪心算法

a.工程计划模型

我们常常碰到这样的问题：完成一个工程需要若干个步骤，每个步骤都有若干种方法，图示——

步骤a  步骤b  步骤c  ... 步骤n
       方法b1 方法c1
方法a1 方法b2 方法c2     方法n1
方法a2 方法b3 方法c3
              方法c4

每个方法有一个权值（如效率、质量），其大小往往和其他步骤中选取的方法有关。有些时候权值无意义，表示方法不可选择。要求给出一个方法组合，是权值和最大。
在这里，暂且把它称作“工程计划”。很多实际问题都可以归纳为这个模型。
对于不同形式的工程计划，我们有不同的解法。
若权值与整个过程或前后步骤的方法选择都有关，我们使用搜索算法——时间复杂度高得吓人。
若每个权值只与上（或下）一步或少数几步的方法选择都有关，我们使用动态规划——有比较高的效率，在下一章会讲到。
若每个权值与其他步骤的方法选择都没有关系，我们使用贪心方法。

b.部分背包与每步最优

强调：每个权值与其他步骤的方法选择都没有关系。这样每步最优就可以得到全局最优——每一步都取最大的权值就可以了。
换而言之，贪心算法要求，局部的贪心选择，可以组成全局的最优解。
在实际问题中，这是需要证明的。如果这个无法证明，贪心算法所得的解不是最优解，一般只是较优解（较优解可为搜索剪枝提供方便）。

下面是贪心算法最经典的例子：部分背包问题。（下一章会讲到另外两种背包问题。）
问题：有N件物品和一个最大载重为M的背包，每件物品都有相应的重量和价值。现要求给出一个存放方案，使背包中物品总价值最大。部分背包要求，每件物品都可只装入它的一部分（部分重量有成比例的部分价值）。所涉及到的数字均为整数。
（注：有时该问题表述为体积形式，即背包体积有限，每件物品有体积和价值。在本系列我选择表述为重量形式。）
思路：背包中物品总价值最高，即单位重量物品价值最高。显然，应该多装单位重量价值高的物品。这样，我们先装入单位重量价值最高的物品，再装入第二高的……直到重量达到M（有必要时最后一件物品只装一部分），已达到物品总价值最高。
这个证明应该很严谨吧～
该算法时间复杂度O(n)，效率很高；而且实现很容易。这些是贪心法最大的特点。

很多竞赛题看似可以用贪心法，其实贪心法得不到最优解，原因是每一步的选择对其他步骤有影响。
数字三角形问题：有一个数字三角形（如下图）。现有一只蚂蚁从顶层开始向下走，每走下一级时，可向左下方向或右下方向走。求走到底层后它所经过的数的最大值。

    1
   6 3
  8 2 6
 2 1 6 5
3 2 4 7 6

如果用贪心法，每次向最大的方向走，得到结果为1+6+8+2+3=20。可是明明还有另一条路，1+3+6+6+7=23。
问题出在哪？每次的选择对后面的步骤会有影响！第三级选了8，就选不到第四、五级较大的数了。
这个问题正确的解法会在下一章介绍。
有一个很实用的小技巧：竞赛题会给出数据规模。通过数据规模，我们可以大致判断该用何种算法。贪心算法可承受的数据规模很大，一般都会上万。如果给出的数据规模是100或1000，优先考虑动态规划吧。

c.构造贪心算法

构造与证明是贪心算法的难点，常常要求我们要有敏锐的观察力、多角度思考的变通能力、丰富的数学知识和推理能力。
下面举几个贪心算法的例子，供大家揣摩、掌握规律。

删数问题：给出一个N位的十进制高精度数，要求从中删掉S个数字（其余数字相对位置不得改变），使剩余数字组成的数最小。
算法构造：
1.每次找出最靠前的这样的一对数字——两个数字紧邻，且前面的数字大于后面的。删除这对数字中靠前的一个。
2.重复步骤1，直至删去了S个数字或找不到这样的一对数。
3.若还未删够S个数字，则舍弃末尾的部分数字，取前N-S个。
证明思路：显然，在只删一个数字时，唯有步骤1的方法能使数变小；可推理得出，删多个数字时，所有最优的方法都可看做是对步骤1的重复。也就是说，以上方法是最优策略之一。
在文末的附件中给出了这个算法的源代码。

工序问题：n件物品，每件需依次在A、B机床上加工。已知第i件在A、B所需加工时间分别为A[i]、B[i]，设计一加工顺序，使所需加工总时间最短。
算法构造：
1.设置集合F、M、S：先加工F中的，再加工M中的，最后加工S中的。
2.对第i件，若A[i]>B[i]，则归入S；若A[i]=B[i]，则归入M。
3.对F中的元素按A[i]升序排列，S中的按B[i]降序排列。
证明思路：
1.F中的能“拉开”A、B加工同一件工件的结束时刻，为后面的工件加工“拉开时间差”，利于节省总时间。S中的刚好相反。因而，F中元素放在最前一定是最优策略之一。
2.F中A[i]小的前置，可以缩短开始时B的空闲时间，但会使F所有工件“拉开的时间差”缩短。不过可以证明，后者带来的损失不大于前者获得的优势。对称地，对S也一样。因而步骤3是可行的。

种树问题：一条街道分为n个区域（按1-n编号），每个都可种一棵树。有m户居民，每户会要求在区域i-j区间内种至少一棵树。现求一个能满足所有要求且种树最少的方案。
算法构造：
1.对于要求，以区间右端（升序）为首要关键字，左端（升序）为次要关键字排序。
2.按排好的序依次考察这些要求，若未满足，则在其最右端的区域种树，这时可能会满足多个要求。
证明思路：解法并不唯一，关键是证明没有比该解法更好的解法。按步骤1排序之后，会发现对于每个要求，在最右边的区域内种树所得的结果总不会差于在其他区域种树。至于为什么这样排序，留给你——读者们思考吧。
在文末的附件中给出了这个算法的源代码。

习题
贪心方法的习题 ——感谢 深蓝评测系统 提供习题

附件：删数问题、种树问题解法源文件
抱歉，只有对本站任何文章发表过评论才能阅读隐藏内容。
未提及的经典贪心问题（点击这里查看）合并果子 股票问题

本文由 最后的叶子 创作，转载或引用前请联系我们。

相关文章：

1. NOIP实用算法 目录
2. NOIP实用算法·教程 下载版
3. 五年NOIP提高组复赛算法及难度分析
4. NOIP实用算法·教程 下载版 2.0
5. NOIP实用算法 下载版 纠错通知

2009年7月27日 星期一