当前位置:首页 >> >>

NOI导刊-贪心与分治_图文

贪心与分治

贪心方法

? 按照当前的状态,选择最好的决策,这就是贪 心法。在实际的应用中,人们往往不可能精确 计算出怎样才是最好的决策,只能凭借往常的 经验,保证每一步都是最好的选择。在解题的 过程中,这样的算法一般是比较容易想到并且 易于编程实现的。能够使用贪心算法解决的问 题,必然是每次都进行最优的选择,并且通过 证明其得到的最后结果也是最优的。

? 反之,如果不能证明每次进行最优选择后,最 终会得到最优的结果,就不能使用贪心算法。 其实,大部分的问题都是不能使用贪心算法的 ,
? 简单的例子:现有10元、7元、2元、1元四种 纸币,使用的张数不限,需要用这四种纸币凑 成p元钱,怎样用最少的张数达到此要求。

? 此题我们很容易就想到了贪心的算法,即每次 尽量选面值大的纸币。但是,在p=14时,贪 心算法的结果为14=10+2+2,而最优结果为 14=7+7,贪心显然是不对的。然而,如果我 们将其中的7元纸币换成5元纸币,贪心算法 却又是对的。这就需要我们用证明来判断了。

例题1 罚款问题
? 现有一台机器以及n项要完成的工作,该 机器每完成一项工作需要1的单位时间,而工 作i如果没有在t[i]的时间内完成,将会受到 c[i]的罚款。求怎样安排工作的顺序,使完成 工作后总的罚款数最少。

分析
? 要使罚款最少,我们显然应尽量完成c[i]值较 大的工作。
? 此时,我们可以将工作按c[i]从大到小进行排 序,然后按照排好的顺序依次对工作进行安排 ,安排的规则为:使处理工作i的时间既在t[i] 之内,又尽量靠后;如果t[i]之内的时间都已经 排满,就放弃处理此项工作。
?

证明
假设按照上述方法得到的解不是最优的,那 么必然存在某个工作j应当安排到处理的过程 中,却没有得到安排。假设我们要将该工作 安排进去,由于时间t[j]内都已经排满,就必 然需要将一个已安排的工作k与之替换,而 c[k]>=c[j],这样替换显然会增加罚款的数额 。因此,除上述安排方法以外的安排方法都 不会使罚款的数额减少,可得上述方法得到 的结果是最优的。

例题2: INT(整数区间)
定义 一个整数区间[A,B],A﹤B,是一个从A 开始,至B结束的连续整数的集合。 任务是从文件中读取区间的个数及其对它们的 描述,找出满足下述条件的所含元素个数最 少的集合中元素的个数:对于每一个区间, 都至少有两个不同的整数属于该集合。

? 输入:
? 文本文件INT.IN的首行包括区间的数目N, 1≦N≦10000。接下来的N行,每行包括两个 整数A,B,被一空格隔开,0≦A≦B≦10000 ,它们是某一个区间的开始值和结束值。
? 输出:最少元素数目。

? 示例输入: ?4 ? 36 ? 24 ? 02 ? 47 ? 输出: ?4

分析
? 本题 “会场安排”问题十分相似,可以用同样 的贪心方法:按照所有区间的结束位置排序, 结束位置相同的项,开始位置小的项在前。从 区间1到区间n进行循环,对于当前区间,若集 合中的数不能覆盖它,则从区间末尾向前扫描 ,若当前数未在集合中出现,则将该数加入集 合,直至使集合能覆盖该区间为止。

示例: 【0,1,2】 【2,3,4】 【3,4,5,6
】【4,5,6,7】
【】 【2】 【2 ,1】 【2,1,4】 【2,1,4,6】

上述算法的指导思想是在某一区间中排 列越靠后的数对以后区间的影响越大, 即它在以后区间出现的可能性越大,但 未经严格数学证明
?

具体实现
? 由于pascal规定的集合类型只有[0..255], 因此在实现时不能使用集合作数据结构,用 数组直接保存也不行,因为在数组中查找数 据相当费时,注意到每个区间中的数大小不 超过10000,可用一个下标为[0..10000]的 布尔型数组标记该数是否出现过,从而解决 这一问题。

例题3:零件分组
? 某工厂生产一批棍状零件,每个零件都有一定的长度(Li)和重量(Wi)。 现在为了加工需要,要将它们分成若干组,使每一组的零件都能排成一个长 度和重量都不下降(若i<j,则Li<=Lj,Wi<=Wj)的序列。请问至少要分成 几组?
输入:第一行为一个整数N(N<=1000),表示零件的个数。第二行有N对正 整数,每对正整数表示这些零件的长度和重量,长度和重量均不超过10000 。
输出:仅一行,即最少分成的组数。 样例(STICK.IN) ?5 ? 8438239735 ? STICK.OUT ?2

例题4:乘船问题(HNCOI)
? 有N个人需要乘船,而每船最多只能载 两人,且必须同名或同姓。求最少需要多 少条船。

问题分析
? 看到这道题,很多人都会想到图的数据结构 :将N个人看作无向图的N个点,凡同名或同 姓的人之间都连上边。
? 要满足用船最少的条件,就是需要尽量多的 两人共乘一条船,表现在图中就是要用最少 的边完成对所有顶点的覆盖。这就正好对应 了图论的典型问题:求最小边的覆盖。所用 的算法为“求任意图最大匹配”的算法。

分析
? 使用“求任意图最大匹配”的算法比较 复杂(要用到扩展交错树,对花的收缩等 等),效率也不是很高。因此,我们必须 寻找一个更简单高效的方法。
? 首先,由于图中任两个连通分量都是 相对独立的,也就是说任一条匹配边的 两顶点,都只属于同一个连通分量。因 此,我们可以对每个连通分量分别进行 处理,而不会影响最终的结果。

? 同时,我们还可以对需要船只s的下限进行估 计:
? 对于一个包含Pi个顶点的连通分量,其最小覆 盖边数显然为[Pi/2]。若图中共有L个连通分量 ,则s=∑[Pi/2](1<=i<=L)。
? 然后,我们通过多次尝试,可得出一个猜 想:
? 实际需要的覆盖边数完全等于我们求出的 下限∑[Pi/2](1<=i<=L)。

? 采用图的数据结构得出的算法为:
每次输出一条非桥的边,并从图中将边 的两顶点删去。
此算法的时间复杂度为O(n3)。 (寻找一条非桥边的复杂度为O(n2),寻找覆盖
边操作的复杂度为O(n))

采用树结构解决
? 见文档

例题5:通讯保卫战
? 见文本

例题6:猜数游戏
? 猜数游戏是一个古老的智力游戏。一个 游戏者A首先想出一个数x(1? x ? n), 让另一个游戏者B来猜。现在由你扮演游
戏者B,用尽可能少的次数猜出x,并且 你所猜的数中大于x的数不能超过m个。

例题7:汤姆的游戏
? 在给定平面上N个图形(矩形或圆)以及M 个点后,请你求出每个点在多少个矩形 或圆内部(这里假设矩形的边都平行于坐 标轴)。
? (N<=200000,M<=10000)


更多相关标签: