1、 算法设计与分析 第 05章 贪心算法第05章贪心算法基本思想n 通过作出在当前看来最优的选择（贪心选择），将原问题规模缩小，如此反复，直至得到最终解。n 贪心算法并非对所有问题都能得到整体最优解。第05章贪心算法活动安排问题n 设有 n个活动 E=e1, e2, , en， 其中每个活动都需要使用某一资源，而在同一时间内该资源只能由一个活动使用，每个活动都有开始时间 si和结束时间 fi(sifi)， 若 ei和 ej满足 sifj或 sjfi， 则称这两个活动相容，要求找出最多相容活动集合 A。第05章贪心算法活动安排问题n 贪心解法： 将所有活动按结束时间排序，得到活动集合 E=e1,e
2、2en； 先将 e1选入结果集合 A中，即 A=e1； 依次扫描每一个活动 ei：如果 ei的开始时间晚于最后一个选入 A的活动 ej的结束时间，则将 ei选入 A中，否则放弃 ei；第05章贪心算法活动安排问题n 解法证明：n 若 E=e1,e2en是按结束时间排序的活动集合，则 e1具有最早的结束时间，设存在一个最优安排 A不包含 e1，并以 ei开始，则易见：A-ei e1也是最优的活动安排；依此类推。第05章贪心算法i si fi1 1 42 3 53 0 64 5 75 3 86 5 97 6 108 8 119 8 1210 2 1311 12 140 1 2 3 4 5 6 7
3、8 9 10 11 12 13 14结果：选中的任务为： 1、 4、 8、 11第05章贪心算法贪心算法的基本要素n 1、贪心选择性质n 所求问题的整体最优解可由一系列局部最优选择得到；n 动态规划是由子问题的解得到当前问题的解；贪心算法则是由当前问题的局部最优解导出子问题；n 确定一个问题是否具有贪心选择性质，需要证明问题的一个整体最优解是从贪心选择开始的；n 2、最优子结构性质n 通过局部最优选择，原问题将被化简为类似的子问题；亦即是说，整体最优解中包含了子问题的最优解；第05章贪心算法背包问题n 有一容量为 W的背包，和单价分别为 vi的物品块（均为单位体积）各 ni块， i=1n； 问
4、每种物品应各选择多少块装入背包中，使得背包中的总价值最大？第05章贪心算法0-1背包问题n 有一容量为 W的背包，和一批体积分别为 wi， 价值为 vi的物品， i=1n； 问将哪些物品装入背包，使得背包中的总价值最大？n 0-1背包问题不满足最优子结构性质，不能用贪心法来求解，而应用分治法求解。分治规则为：S(w1.n, v1.n, W) = maxS(w1.n-1, v1.n-1, W-wn)+vn, S(w1.n-1, v1.n-1, W)第05章贪心算法哈夫曼算法的证明n 贪心选择性质的证明n 若叶结点 x,y是被选中合并的结点，即 x,y具有最小权值，则n 1. x、 y是结果树上深度最大的两个结点，且互为兄弟；n 2. 必存在最优二叉树以 x,y为深度最大的两个结点，且互为兄弟（编码最长，且只有最后一位编码不同）；n 证明：显然，总可通过交换 x,y到最深的一对兄弟结点，得到满足条件的最优二叉树；
