1、算法设计与分析第四章 贪婪算法杨圣洪13007432216(M)， 346260267(Q)什么是 贪婪 ？ (问 ) 战国策 齐策四 ：左右皆恶之，以为贪而 不知足 。 高级汉词典 对财物、钱等充满非同寻常的 强烈欲望greedy:Excessively desirous of acquiring or possessing, especially wishing to possess more than what one needs or deserves.特别渴望获取或占用，尤其希望占有超出所需的物品 2不 考虑 全局最优 ， 只 考虑 局部最优 。这种算法往往非常简单，而效率最高，并且
2、如果问题具有 最优子结构 ，即 整体最优 时 局部也是最优 ，那么多数情况下能取得到 整体最优解 ，至少能得到整体最优解的 近似解 。十八大三中全会 ：使 市场 在资源配置中起 决定性 作用。“ 市场 ” 即 “ 贪婪算法 ”，各经济体做出使自身收益最大的决策， 最终能使整个社会达到整体最优，或至少近似最优， 改革 就成功了。计划经济 追求 整体最优，往往 牺牲 局部最优。什么贪婪算法？3实例 1找零钱问题小钱有： 5角、 2角、 1角、 5分、 2分、 1分找回 6角 7分钱： 5角、 1角、 5分、 2分各一个方法：选出不超过 6角 7分的最大面值 5角，剩下 1角 7分，再找出不超此值最
3、大面值 1角每次都是最大面值，这就是 贪婪算法 。 4实例 2-活动安排Si事件 i的 start时间Fi事件 i的 finish时间只有 当前事件 i完成以后， 下件事情 j才能做！在 互不干扰前提 下，安排尽可能多的活动。按结束时间从早到晚即 低到高 排序？最早结束的最先选定，i 1 2 3 4 5 6 7 8 9 10 11Si 1 3 0 5 3 5 6 8 8 2 12fi 4 5 6 7 8 9 10 11 12 13 145i 1 2 3 4 5 6 7 8 9 10 11Si 1 3 0 5 3 5 6 8 8 2 12fi 4 5 6 7 8 9 10 11 12 13 14
4、完成时间的 升序排列 (O(nlog2n)后事开始时间 si晚 于 =前事的结束时间 fj6i 1 2 3 4 5 6 7 8 9 10 11Si 1 3 0 5 3 5 6 8 8 2 12fi 4 5 6 7 8 9 10 11 12 13 14int GS(int s, int f, int a)int n=s.length-1;a1=1; /事件 1先上int j=1; /当前事件编号int count=1; /能排的事件数for (int i=2;i=fj) ai=1;j=i;count+;else ai=0;return count;7实例 3： 0-1背包问题与背包问题0-1背包
5、问题背包问题 ： 给定 n种物品和一个背包。 Wi为体积，价值为 Vi，背包的容量为 C。如何选择品，使得背包中物品的总价值最大？ 物品 i： 装 (1)或不装 (0)。背包问题 : 与 0-1背包问题类似，所不同的是在选择物品 i装入背包时，可以选择物品 i的 一部分 ，而不一定要 全部 装入背包， 1in。都具有最优子结构性质，背包问题 可以用 贪心 算法求解，0-1背包 问题却不能用 贪心 求解。 8背包问题的贪心算法 void Knapsack(int n,float M,float v,float w,float x)Sort(n,v,w); /按按 v/w即单位价值降序排序即单位价值降序排序 (O(nlog2n)int i; /最值钱最值钱 的排在的排在 最前面最前面for (i=1;ic) break; /超过包的剩余体积则中止超过包的剩余体积则中止xi=1; /物品物品 i全部放入全部放入c=c-wi; /重新计算包的重新计算包的 剩余体积剩余体积if (ic) break; xi=1;c=c-wi; if (i=n) xi=c/wi; 按 6, 5, 3从高到低中间红字为 0-1背包不正确！背包问题W=10,20,30V=60,100,120单价单价 =6,5,4 高高 低低 排队排队6 5 3 10
