人民币找零问题.doc

文档介绍：证明人民币找零问题的贪心算法的正确性
问题的提出
日常生活当中, 买卖东西的时候经常遇到找零钱问题, 例如超市购物付款时,收银员就会根据收款机给顾客找零钱。我们不难发现收银员找零时,总是先支付顾客最大面值的人民币, 要是金额不足再支付面值小一点的, 直到找满为止。
很显然,这样的找零方法符合贪心方法,但是收银员用这样的贪心方法找给顾客零钱时,是否就能使零钱的张数达到最少?有没有更好的策略,使张数比用贪心方法的更少?这个问题就有待我们考证。

贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法, 它总是做出在当前看来是最优的选择, 也就是说贪心策略并不是从整体上加以考虑, 它所做出的选择只是在某种意义上的局部最优解算法。

贪心算法通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部最好选择,即贪心选择。
但是,从许多可以用贪心算法求解的例子中看到这类问题一般具有2个重要的性质:贪心选择性质和最优子结构性质。
贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素。
贪心算法是以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。
最优子结构性质
当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。


贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行, 根据某个优化测度, 每一步都要确保能获得局部最优解。每一步只考虑一个数据, 他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中, 直到把所有数据枚举完, 或者不能再添加算法停止。


实现的过程
(1)应用同一规则,将原问题变为一个相似的、但规模更小的子问题。
(2)从问题的某一初始解出发;
While (能朝给定总目标前进一步)
求出可行解的一个解元素;
(3)由所有解元素组合成问题的一个可行解;
贪心算法的核心
贪心算法的核心问题是选择能产生问题最优解的最优度量标准, 即具体的贪心策略。
人民币找零问题采用贪心算法的正确性
人民币找零问题能否采用贪心算法,其核心思想就是验证人民币找零问题是否具备贪心算法的两个基本要素,即是否具备“贪心选择性质”和“最优子结构性质”。
为什么要验证贪心算法的两个基本要素?这是因为贪心算法不是对所有问题都能得到整体最优解,但对规范相当广的许多问题它能产生整体最优解。在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好的近似解。
若能验证人民币找零问题可以采用贪心算法这个前提,接着我们就证明用贪心算法得到的贪心解是一个最优解,那么这个问题就迎刃而解。即人民币找零问题采用贪心算法是能得到最优解的。
验证人民币找零问题