算法设计与分析学习提纲，第五章 贪婪法.doc

PAGE PAGE 16 第五章 贪婪法 例5.1 货币兑付问题：用最少的货币张数支付现金。 集合表示张面值为的货币，， 出纳员需支付的现金为，从中选取一个最小的子集，使得 并且 用向量表示中所选取的货币，使得： 那么，出纳员支付的现金必须满足： （5.0.1） 并且使得： （5.0.2） 向量称为问题的解向量， 所有向量的全体称为问题的解空间。 （5.0.1）式称为问题的约束方程， （5.0.2）式称为问题的目标函数。 满足约束方程的向量称为问题的可行解。 满足目标函数的向量称为问题的最优解。 5.1 贪婪法引言 5.1.1 贪婪法的设计思想 贪婪法的设计方法描述如下： greedy(A,n) { solution = ?; for (i=1;in;i++) { x = select(A); if (feasible(solution,x)) solution = union(solution,x); } return solution; } 适于贪婪法求解的问题，具有两个重要性质：贪婪选择性质和最优子结构性质。 贪婪选择性质，是指所求问题的全局最优解，可以通过一系列局部最优的选择来达到。 例：从10张10元、10张5元、10张1元、10张5角、10张2角、10张1角的货币中兑付57元8角 集合顺序表示货币； 向量表示支付给客户的货币。 第一步挑出的货币集合，局部解， 问题简化为在集合中挑选货币、付出47元8角 在以后的步骤中，可以用同样的方法进行挑选，并能得到问题的全局最优解。 最优子结构：指问题的最优解，包含它的子问题的最优解。 付给客户的货币集合的最优解是。 第一步所简化了的子问题的最优解是。，并且。所以，出纳员付钱问题具有最优子结构性质。 5.1.2 贪婪法的例子，货郎担问题 例5.2 货郎担问题。5个城市，费用矩阵如图5.1所示。 图5.1 5个城市的费用矩阵 总是选择费用最小的路线前进，选择的路线是1?4?3?5?2?1，总费用是14。 只选择一个城市作为出发城市，所需时间是。 个城市都可以作为出发城市，所需时间是。 从城市1出发的最优的路线是1?2?5?4?3?1，总费用只有13。 图5.2 货郎担问题的求解过程 5.2 背包问题 载重量为的背包，重量为、价值为的物体，，把物体装满背包，使背包内的物体价值最大 物体可以分割的背包问题，及物体不可分割的背包问题，把后者称为0/1背包问题。 5.2.1 背包问题贪婪算法的实现 解向量 ：物体被装入背包的部分，， ：物体没被装入背包； ：物体被全部装入背包 约束方程： （5.2.1） 目标函数： （5.2.2） 价值重量比最大：既使目标函数的值增加最快，又使背包载重量的消耗较慢。 数据结构： typedef struct { float p; /* n个物体的价值 */ float w; /* n个物体的重量 */ float v; /* n个物体的价值重量比 */ } OBJECT; OBJECT instance[n]; float x[n]; /* n个物体装入背包的份量 */ 算法5.1 贪婪法求解背包问题 输入：背包载重量M,存放n个物体的价值p、及重量w信息的数组instance[] 输出：n个物体被装入背包的份量x[],背包中物体的总价值 1. float knapsack_greedy(float M,OBJECT instance[],float x[],int n) 2. { 3. int i; 4. float m,p = 0; 5. for (i=0;in;i++) { /* 计算物体的价值重量比 */ 6. instance[i].v = instance[i].p / instance[i].w; 7. x[i] = 0; /* 解向量赋初值 */ 8. } 9. merge_sort(instance,n); /* 按关键值v的递减顺序排序物体 */ 10. m = M; /* 背包的剩余载重量 */ 11. for (i=0;in;i++) { 12. if (instance[i].w=m) { /* 优先装入价值重量比大的物体 */ 13. x[i] = 1; m -= instance[i].w; 14. p += instance[i].p