欢迎来到天天文库
浏览记录
ID:59320395
大小:14.00 KB
页数:1页
时间:2020-09-05
《证明人民币找零问题贪心算法正确性.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,即m3、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)均应为最大数量了,所以贪心算法得到的解是最优解,即满足贪心选择性质。综上所述,人民币找零问题满足贪心算法。
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)均应为最大数量了,所以贪心算法得到的解是最优解,即满足贪心选择性质。综上所述,人民币找零问题满足贪心算法。
此文档下载收益归作者所有