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

证明人民币找零问题贪心算法正确性由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“证明贪心算法的正确性”。

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

问题提出：

根据人们生活常识，我们到商店里买东西需要找零钱时，收银员总是先给我们最大面值的，要是不够再找面值小一点的，直到找完为止。这就是一个典型的贪心选择问题。问题描述：

当前有面值分别为100 元、50 元、20 元、10 元、5元、1元, 5角, 2角、1角的人民币。证明人民币在找零时（1-99元）符合贪心算法，即证明此问题满足贪心算法的两个基本要素：即最优子结构性质和贪心选择性质。

问题证明：

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。在人民币找零问题中，其最优子结构性质表现为：

设c[i]是各面额人民币使用的数量，S[i]是商品价格为n时的最优解，数量为K。现在设某面值的人民币数量减一：S[j]=S[j]-1，则新的S[i]为n-c[j]的最优解，纸币数K-1.否则，设T[i]是n-c[j]的最优解，纸币数为m，即m

设纸币面额100,50,20,10,5,2,1元的数量依次为A,B,C,D,E,F,G，则根据贪心算法思想得到的解应依次保证max（A），max（B），max（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）均应为最大数量了，所以贪心算法得到的解是最优解，即满足贪心选择性质。

综上所述，人民币找零问题满足贪心算法。