5贪心算法程序.ppt

文档介绍：2017-2-15 1ACM 程序设计信息学院 2017-2-15 2今天, 今天, 你了吗? AC 2017-2-15 3贪心算法( Greedy Algorithm ) 2017-2-15 4找零钱找零钱?出纳员手里有 10元, 5元, 1元, 5角, 2 角, 1角的钱,现有客户付钱,应找给他57元8角,该如何找钱能使钱的张数最少? 2017-2-15 5找零钱( 找零钱( 2 2) ) ?如果面值只有分别为 1分, 5分, 11分的硬币,那么找钱的时候可否用贪心法? ?比如希望找回 15分,如果采用贪心法?应先找 1个11分的,然后是 4个1分的, ?显然这不是最优的。 2017-2-15 6 2439 2439 找钱问题找钱问题?买火车票时经常会碰到找钱问题。售票员手中有 50、20、10、5、1元的钱币, 你知道怎么找钱才能使找回的零钱张数最少吗? 2511 Delete Number 2511 Delete Number 2017-2-15 7还记得还记得 ZSTUOJ_1270 ZSTUOJ_1270 吗? 吗? FatMouse' Trade 2017-2-15 8所谓所谓““贪心算法贪心算法””是指: 是指: 在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优, 需要证明)。 2017-2-15 9特别说明: 特别说明: 若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!! 2017-2-15 10用事实说话用事实说话————