《算法设计与分析》ch4 贪心法.pptx

第4章 贪心算法;2;贪心算法（1）;4;贪心算法（2）;贪心算法（3）;;8;9;10;4.1 活动安排问题;12;13;14;15;4.1 活动安排问题;17;18;19;20;21;;23;24;25;26;27;28;29;30;31;32;4.3. 0-1背包和一般背包问题;4.3. 0-1背包和一般背包问题;35;36;37;10;39;40;;哈夫曼算法;引子1;if (score60) return“不及格”; else if (score70) return “及格”; else if (score80) return “中等”; else if (score90) return “良好”; else return “优秀”; ; 在实际生活中，学生的成绩在五个等级上的分布是不均匀的。假如其分布规律如下表所示：;;例如，邮局发电报，发送方将原文转换成二进制字符串，接收方将二进制字符串还原成原文。 原文 电文（二进制字符串） 原文;49; 数据压缩是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率的一种技术方法。或按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间。数据压缩包括有损压缩和无损压缩。 ;无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同； 无损压缩用于要求重构的信号与原始信号完全一致的场合。 一个很常见的例子是磁盘文件的压缩。 根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2～1/4。 一些常用的无损压缩算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv Welch)压缩算法。　;有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。 有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。 图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比;数据中间常存在一些多余成分，既冗余度。 如在一份计算机文件中，某些符号会重复出现、某些符号比其他符号出现得更频繁、某些字符总是在各数据块中可预见的位置上出现等，这些冗余部分???可在数据编码中除去或减少。 冗余度压缩是一个可逆过程，因此叫做无失真压缩，或称保持型编码。 ;人们在欣赏音像节目时，由于耳、目对信号的时间变化和幅度变化的感受能力都有一定的极限， 人眼对影视节目有视觉暂留效应，人眼或人耳对低于某一极限的幅度变化已无法感知等， 可将信号中这部分感觉不出的分量压缩掉或“掩蔽掉”。 这种压缩方法同样是一种不可逆压缩。 ;图像压缩属于有损压缩，动态规划章节内容，可查阅 本节主要关注无损压缩，该如何进行无损压缩呢？;例 要传输的原文为ABACCDA设ABCD的编码为A；00B；01C：10D：11 发送方：将ABACCDA 转换成 00010010101100 接收方：将 00010010101100 还原为 ABACCDA;二、相关概念;二叉树：;完全二叉树：;路径： 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 ;树的路径长度： 树中每个结点的路径长度之和。 (完全二叉树是路径长度最短的二叉树);结点的权值： 对结点赋予的一个有意义的数值量。;树的带权路径长度: 树中所有叶子结点的带权路径长度之和;例1：给定4个叶子结点，其权值分别为{2，3，4，5}，可以构造出形状不同的多棵二叉树。 ;哈夫曼编码;哈夫曼编码;前缀编码: 任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。前缀编码保证了在解码时不会有多种可能。 ; 在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。 我们可以利用二叉树来设计二进制的前缀编码。约定左分支表示字符‘0’，右分支便是字符‘1’，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。;证明： 假设某一个叶子x结点的编码是另一个叶子结点y编码的前缀，说明从根结点到叶子结点y中间需经过结点x，从而说明x有左或右子树，这与x是叶子结点矛盾。 那么现在求最短的二进制编码实际上