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

货币找零问题

2024-07-14 21:58:42   231人阅读

已知，中华人民共和国的纸币面额分别为：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


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


联系
我们