贪心选择性质证明(归纳基础) 设S={1,2,…,门}是活动集,活动按截止时间递增 顺序排序 k=1,证明存在最优解包含活动1 任取最优解AA中的活动按照截止时间递增 的顺序排列如果A的第一个活动为方件1, 令A=(A-})儿∪{1}由于行≤后A也是最优解 且含有1
贪心选择性质证明（归纳基础） 设S={1,2,…,n}是活动集，活动按截止时间递增 顺序排序. k=1, 证明存在最优解包含活动1. 任取最优解A, A中的活动按照截止时间递增 的顺序排列. 如果A的第一个活动为j，j≠1, 令A ’= (A−{j })∪{1}, 由于f1≤fj , A ’也是最优解， 且含有1
贪心选择性质证明(归纳步骤) 偎设命题对为真证明对k+1也为真 算法执行到第/步选择了活动h=1,饭…,似根据归纳假 设存在最优解包含=1, 冲中剩下的活动选自集合S=S9们且 位b:UBB5的最优解 若不然,5的最优解为BB米的活动比B多,那么 BU{1,h…,}是S的最优解,且比A的活动多,与A 的最优性矛盾. 根据归纳基础,存在S的最优解B含有S'中的第一个活 动,设为+1,且|B=,于是 { 是原问题的最优解 B1={h,b…,似k+1}∪(B
贪心选择性质证明（归纳步骤） 假设命题对k为真,证明对k+1也为真. 算法执行到第k步, 选择了活动i1=1, i2 , …, ik , 根据归纳假 设存在最优解A包含i1= 1, i2 , … , ik , A中剩下的活动选自集合S ’={ i | i∈S, si≥fk},且 A= {i1 , i2 , … , ik}∪B, B是S ’的最优解. 若不然, S ’的最优解为B*, B* 的活动比B 多，那么 B* ∪{1, i2 , … , ik}是S 的最优解，且比A的活动多,与A 的最优性矛盾. 根据归纳基础，存在S ’的最优解B ’含有S ’中的第一个活 动，设为ik+1, 且|B ’|=|B|, 于是 {i1 , i2 , … , ik} ∪ B ’ ={i1 , i2 , … , ik , ik+1} ∪(B ’-{ik+1})也 是原问题的最优解
Huffman编码问题 ■最优二元(二进制)前缀码 n前缀码 用0-1字符串作为代码表示字符,要求任何字符 的代码都不能作为其它字符代码的前缀 可以采用二叉树结构存储,每个字符作为树叶, 每个前缀码看作根到树叶的路径 输入:n个字符x,巧,…,n 每个字符传输概率f(x1,2,…,n 求:前缀码,使得平均传输一个字符的位数 达到最小
Huffman编码问题 ◼ 最优二元（二进制）前缀码 ◼ 前缀码 ◼ 用0-1字符串作为代码表示字符，要求任何字符 的代码都不能作为其它字符代码的前缀 ◼ 可以采用二叉树结构存储，每个字符作为树叶， 每个前缀码看作根到树叶的路径 ◼ 输入：n个字符x1 , x2 , … , xn， ◼ 每个字符传输概率f (xi ), i=1, 2, … , n ◼ 求：前缀码，使得平均传输一个字符的位数 达到最小
Huffman编码树 a:45;b:13;c12;d16;e:9;5 100 f=-0000, 5 e-0001, a d--001, 30 c-010 b011 1213 a 5 9 4*5%4*9%3*16%+3*12%3*13%1*45%=2.24
Huffman编码树 ◼ a:45; b:13; c:12; d:16; e:9; f:5 f--0000, e--0001, d--001, c--010, b—011, a--1 4*5%+4*9%+3*16%+3*12%+3*13%+1*45% = 2.24