首页 > 代码库 > 贪心算法_活动安排问题_哈弗曼编码

贪心算法_活动安排问题_哈弗曼编码

问题表述:设有n个活动的集合E = {1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活i都有一个要求使用该资源的起始时间si和一个结束时间fi,si < fi 。如果选择了活动i,则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交,则称活动i与活动j是相容的。也就是说,当si >= fjsj >= fi时,活动i与活动j相容。

由于输入的活动以其完成时间的非减序排列,所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说,该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。

算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列,算法只需O(n)的时间安排n个活动,使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列,可以用O(nlogn)的时间重排。

例:设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下:

算法greedySelector 的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动,而空白长条表示的活动是当前正在检查相容性的活动。

若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi,则不选择活动i,否则选择活动i加入集合A中。 

贪心算法并不总能求得问题的整体最优解。但对于活动安排问题,贪心算法greedySelector却总能求得的整体最优解,即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。

活动安排问题实现:

...

 

 

 

 

 哈夫曼编码

 

哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用01串表示各字符的最优表示方式。

 

给出现频率高的字符较短的编码,出现频率较低的字符以较长的编码,可以大大缩短总码长。

 

 

a

b

c

d

e

f

频率(千次)

45

13

12

16

9

5

定长码

000

001

010

011

100

101

变长码

0

101

100

111

1101

1100

 

定长码:

 

  3*(45+13+12+16+9+5) = 300 千位

 

变长码:

 

  1*45+3*13+3*12+3*16+4*9+4*5 = 224 千位

 

 

贪心算法_活动安排问题_哈弗曼编码