程序的设计培训的讲义4贪心算法汇总.ppt

程序设计培训之4: 贪心算法 袁辉勇 2010年1月8日 概述 贪心法也称为贪婪法 算法原理:以当前情况为基础作最优选择, 而不考虑各种可能的整体情况,所以贪心法不 要回溯 算法优点:因为省去了为寻找解而穷尽 所有可能所必须耗费的大量时间,因此算法效 率高 注意:通常使用贪心算法时需要证明 例1:找零钱问题 平时购物找钱时,为使找回的零钱的硬 币数最少,不考虑找零钱的所有各种发表方 案,而是从最