贪心 -- 2




200x200


问题描述赫夫曼编码是一种应用广泛并且非常有效的压缩技术,一般可以压缩掉20%到90%赫夫曼编码使用一张字符出现频度表,记录每个字符出现的频度,根据每个字符出现的频度来进行不定长编码,即对于出现频度大的

#读书笔记    #技术帖    #算法    #算法导论   
问题描述活动选择问题就是对几个相互竞争的活动进行调度,每个活动都要求独占某一资源,要在N个活动中挑选出一个互相兼容的活动的最大子集合 问题分析我们可以首先按照各个活动的结束时间将活动进行排序,对于活动 ai 到 aj,如果兼容活动数不为0并且 ak 是其中的一个被兼容的活动,那么活动的总数 = ai 到 ak 的兼容活动数 + ak 到 aj 的兼容活动数 + 1这样,我们就可以将原问题划分为 ai 到 ak 的兼容活动数 与  ak 到 aj 的兼容活动数 两个子问题来分别计算,因此我们可以使用动态规划算法 但是,对于这个问题,我们可以从另外一个角度考虑,就是寻找 ai 到 ak 的最大兼容子集合的最早结束时间,这样对于aj(j>k),将有最大可能添加到原集合,因为活动是按照各个活动的结束时间递增排序的,因此,我们只要顺序地选择活动就可以得到当前子集的最早结束时间的活动,最终,可以得到全局最优解 算法代码/* * file: m
#读书笔记    #技术帖    #算法    #算法导论   



京ICP备15018585号