首页 > 代码库 > 货币找零问题

货币找零问题

已知,中华人民共和国的纸币面额分别为:100元、50元、20元、10元、5元、2元、1元,输入钱数,输出最小的货币方案。

int main(){    int value[7] = { 100, 50, 20, 10, 5, 2, 1 }, count[7], change;    int i, j, sum;    while (cin >> change, change)    {        for (i = 0; i < 7; i++)        {            count[i] = change / value[i];            change -= count[i] * value[i];        }        sum = 0;        for (i = 0; i < 7; i++)        {            cout <<"value:" <<value[i]<<"===>>count:"<<count[i]<<endl;            sum += count[i];        }        cout << "totalCount:" << sum << endl;    }    return 0;}
View Code

贪心算法在这里之所以总是最优,是因为银行对其发行的硬币种类和硬币面值的巧妙安排

 

如果只有面值分别为1,5和11单位的硬币,而希望找回总额为15单位的硬币,按贪婪算法,应找1个11单位面值的硬币和4个1单位面值的硬币,共找回5个硬币。但最优的解答应是3个5单位面值的硬币。
同理,对于目标是找67分,面值有25、10、5、2、1,目标是所用硬币数量最少。此问题用贪心可得最优解,即每次拿出不会导致总面值超过目标面值的最大面值:25+25+10+5+2=67。
但是,如果换成目标面值10分,面值种类有7、5、1,那么贪心法就不好用了,因为7+1+1+1=5+5。
 
int main(){    int value[11], count[11], change;    int i, n, sum;    while (cin >> n >> change)    {        for (i = 1; i <= n; i++)        {            cin>>value[i];        }        sort(value + 1, value + 1 + n);//# include<algorithm>        for (i = n; i >= 1; i--)        {            count[i] = change / value[i];            change -= count[i] * value[i];        }        sum = 0;        for (i = n; i >= 1; i--)        {            cout <<"value:" <<value[i]<<"===>>count:"<<count[i]<<endl;            sum += count[i];        }        cout << "totalCount:" << sum << endl;    }    return 0;}
View Code


可惜的是,一个问题满足什么样的条件才能保证贪心算法可以得出最优解,对于这个问题,目前还没有一个好的判定方法。即:你只能证明你的方法满足贪心算法的两个基本要素:最优子结构性质和贪心选择性质,所以求出的解是最优解;但你不能证明这个问题用其他的贪心策略也能得出正确解。