可用贪心算法解决的几个基本问题

1、可用贪心算法解决的几个根本问题关键：看问题有没有贪心选择性质和最优子结构性质。有些问题看似是可 以用贪 心算法，但是实际用贪心算法却得不到最优解。构造贪心算法后，需要 一定的证明来 确定它的正确性。常用证明方法：反证法、调整法。几个根本问题：1. 活动安排问题。设有n个活动的集合e=1 , 2,，n,其中每个活动都要求使用同一资 源，如演 讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 都有一个要求使 用该资源的起始时间 si 和一个结束时间 fi, 且 si<fi。如果选择了活动i,那么它在区间si, fi内占用资源。假设区间si, fi 与区间 sj , fj不相交，那

2、么称活动 i 与活动 j 是相容的。也就是说，当 sj > 或 si >fj 时, 活动 i 与活动 j 相容。活动安排问题就是要在所给的活动集合中选出 最大的 相容活动子集合。解决方法：先选择结束时间最早的那一个活动 , 然后 往后依次查找结束时间最近的不冲突的活动参加。2. 可以解决背包问题，不能解决 0-1 背包问题。0-1 背包问题：给定 n 种物品和一个背包。物品 i 的重量是 Wi, 其价值为 Vi, 背包的容量 为 C。 应如何选择装入背包的物品 , 使得装入背包中物品的总价值最大？在选择 装入背 包的物品时，对每种物品 i 只有 2 种选择，即装入背包或不装入背包。

3、不 能将物品 i 装 入背包屡次 , 也不能只装入局部的物品i。背包问题 :与 0-1 背包问题类似 , 所不同的是在选择物品 i 装入背包时 , 可以选择物品 i 的一 局部，而不一定要全部装入背包，1< i *解决方法：求每个物品的价值重量比 , 即价值 /重量。然后添加价值重量比最大的物品 , 添加结束如果未到达重量上限 , 再添加价值重量比次大的。3. 最优装载问题有一批集装箱要装上一艘载重量为 c 的轮船。其中集装箱 i 的重量为 Wi。最优装载问题要求确定在装载体积不受限制的情况下 , 将尽可能多的集装 箱装上 轮船。解决方法：每次装重量最轻者。4. 哈夫曼编码给出现频率高的

4、字符较短的编码 , 出现频率较低的字符以较长的编码。对 每一个 字符规定一个 0,1 串作为其代码 , 并要求任一字符的代码都不是其它字符 代码的前缀。 这种编码称为前缀码。5. Dijkstra 算法给定带权有向图 G =V,E ， 其中每条边的权是非负实数。另外，还给定 V 中 的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。根本思想是，设置顶点集合 S 并不断地作贪心选择来扩充这个集合。一个 顶点 属于集合 S 当且仅当从源到该顶点的最短路径长度。6. 求最小生成树的 Prim 算法和 Kruskal 算法

5、。 7.多机调度问题。 要求给出一种作业调度方案，使所给的 n 个作业在尽可能短的时间内由 m 台机 器加工处理完成。这个问题是 NP 完全问题，到目前为止还没有有效的解法。采用最长处理时 间作 业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。解决方案：当 n>m 时，首先将 n 个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为 O(nlogn) 。8.埃及分数问题。设 a、 b 为互质正整数， avb 分数 a/b 可用以下的步骤分解成假设干个单位分 数之 和：步骤一:用b除以a,得商数q1及余数r1。(r1=b - a*q1)步骤二：把 a/b 记作:a/b=1/(q1+1)+(a-r