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

关键：看问题有没有贪心选择性质和最优子结构性质。有些问题看似是可以用贪心算法，但是实际用贪心算法却得不到最优解。构造贪心算法后，需要一定的证明来确定它的正确性。常用证明方法：反证法、调整法。

几个基本问题：

1. 活动安排问题。

设有n个活动的集合e={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间f_i,且s_i<f_i。如果选择了活动i，则它在区间[s_i，f_i]内占用资源。若区间[s_i，f_i]与区间[s_j，f_j]不相交，则称活动i与活动j是相容的。也就是说，当s_j≥fi或s_i≥f_j时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

解决方法：先选择结束时间最早的那一个活动，然后往后依次查找结束时间最近的不冲突的活动加入。

2. 可以解决背包问题，不能解决0-1背包问题。

0-1背包问题：

给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？

在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。

背包问题:

与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。

解决方法：求每个物品的价值重量比，即价值/重量。然后添加价值重量比最大的物品，添加结束如果未达到重量上限，再添加价值重量比次大的。

3. 最优装载问题

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

解决方法：每次装重量最轻者。

4. 哈夫曼编码

给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码。对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。

5. Dijkstra算法

给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

6. 求最小生成树的Prim算法和Kruskal算法。

7. 多机调度问题。

要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

这个问题是NP完全问题，到目前为止还没有有效的解法。采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。

解决方案：当n>m时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。

8. 埃及分数问题。

设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：

步骤一: 用b 除以a, 得商数q1 及余数r1。 (r1=b - a*q1)

步骤二：把a/b 记作:a/b=1/(q1+1)+(a-r)/b(q1+1)

步骤三：重复步骤2，直到分解完毕

例：3/7=1/3+2/21=1/3+1/11+1/231

13/23=1/2+3/46=1/2+1/16+1/368

思路：也是贪心思维，以 b/a取整+1 作为一个分解因子，其实是选取了值最大的分子为1的分解。