文档介绍：肂证明人民币找零问题的贪心算法的正确性肁螈问题的提出莇日常生活当中,买卖东西的时候经常遇到找零钱问题,例如超市购物付款时,收银员就会根据收款机给顾客找零钱。我们不难发现收银员找零时,总是先支付顾客最大面值的人民币,要是金额不足再支付面值小一点的,直到找满为止。袄很显然,这样的找零方法符合贪心方法,但是收银员用这样的贪心方法找给顾客零钱时,是否就能使零钱的张数达到最少?有没有更好的策略,使张数比用贪心方法的更少?这个问题就有待我们考证。,它总是做出在当前看来是最优的选择,也就是说贪心策略并不是从整体上加以考虑,它所做出的选择只是在某种意义上的局部最优解算法。。它所做的每一个选择都是当前状态下局部最好选择,即贪心选择。莆但是,从许多可以用贪心算法求解的例子中看到这类问题一般具有2个重要的性质:贪心选择性质和最优子结构性质。螆莁***,即贪心选择来达到。这是贪心算法可行的第一个基本要素。膄贪心算法是以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。膀对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,根据某个优化测度,每一步都要确保能获得局部最优解。每一步只考虑一个数据,他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加算法停止。(1)应用同一规则,将原问题变为一个相似的、但规模更小的子问题。袁(2)从问题的某一初始解出发;蒇While(能朝给定总目标前进一步)芅求出可行解的一个解元素;蒂(3)由所有解元素组合成问题的一个可行解;,即具体的贪心策略。羀羅莅肀肀人民币找零问题采用贪心算法的正确性莆人民币找零问题能否采用贪心算法,其核心思想就是验证人民币找零问题是否具备贪心算法的两个基本要素,即是否具备“贪心选择性质”和“最优子结构性质”。袃为什么要验证贪心算法的两个基本要素?这是因为贪心算法不是对所有问题都能得到整体最优解,但对规范相当广的许多问题它能产生整体最优解。在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好的近似解。肃若能验证人民币找零问题可以采用贪心算法这个前提,接着我们就证明用贪心算法得到的贪心解是一个最优解,那么这个问题就迎刃而解。即人民币找零问题采用贪心算法是能得到最优解的。“贪心选择性质”袂芀人民币当前的面值有100元、50元、20元、10元、5元、