证明人民币找零问题贪心算法正确性.doc

证明人民币找零问题贪心算法正确性.doc

ID:59320395

大小:14.00 KB

页数:1页

时间:2020-09-05

证明人民币找零问题贪心算法正确性.doc_第1页
资源描述:

《证明人民币找零问题贪心算法正确性.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、证明人民币找零问题贪心算法的正确性问题提出:根据人们生活常识,我们到商店里买东西需要找零钱时,收银员总是先给我们最大面值的,要是不够再找面值小一点的,直到找完为止。这就是一个典型的贪心选择问题。问题描述:当前有面值分别为100元、50元、20元、10元、5元、1元,5角,2角、1角的人民币。证明人民币在找零时(1-99元)符合贪心算法,即证明此问题满足贪心算法的两个基本要素:即最优子结构性质和贪心选择性质。问题证明:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。在人民币找零问题中,其最优子结构性质表现为:设c[i]是各面额人民币使用的数量,S[i]是商品价格为n时的最优

2、解,数量为K。现在设某面值的人民币数量减一:S[j]=S[j]-1,则新的S[i]为n-c[j]的最优解,纸币数K-1.否则,设T[i]是n-c[j]的最优解,纸币数为m,即m

3、ax(C),max(D),max(E),max(F),max(G)。假设存在更优的算法,使得所用的纸币数更少,即数量至少小于或等于A+B+C+D+E+F+G-1。那么在纸币总数减少的情况下保证总额不变只能增大相对大面额纸币的数量并减少小面额纸币数量。而由贪心算法知max(A)已经是最大的了,以此类推,max(B),max(C),max(D),max(E),max(F)均应为最大数量了,所以贪心算法得到的解是最优解,即满足贪心选择性质。综上所述,人民币找零问题满足贪心算法。

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。