湖大CG满分教程：作业训练四编程题16. 最小钱币数（贪心算法）

【问题描述】

阿迪有很多钱。他在银行里有n元。出于安全考虑，他想用现金取款（此处不透露原因）。钞票的面额是1，5，10，20，100元。取出全部余额后能收到的最小钞票数是多少？

【输入形式】

输入一个正整数n，（1≤n≤109）
【输出形式】

阿迪能收到的最小钞票数
【样例输入1】
125
【样例输出1】
3
【样例输入2】
43
【样例输出2】
5
【样例输入3】
1000000000
【样例输出3】
10000000
【样例说明】

本题可以直接使用贪心策略（优先尽可能多选择大面额的钞票）解决：主要原因是后一个的权值（这里就是纸币面值）是前一个的2倍或以上。

可以思考一下如果货币的类型是1,9,10元三种，要求凑出18元，你可能就会发现贪心算法出错了！
#include<iostream> using namespace std; int main() { int n,sum=0; cin>>n;
while(n) { if(n>=100) { sum+=n/100; n%=100; } if(n<100&n>=20) { sum+=n/20;
n%=20; } if(n<20&&n>=10) { sum+=n/10; n%=10; } if(n<10&&n>=5) { sum+=n/5; n%=5;
} if(n<5&&n>=1) { sum+=n/1; n%=1; } } cout<<sum; return 0; }

• « 上一篇：通俗易懂讲解CPU、GPU、FPGA的特点
• » 下一篇：好看的登录界面（2）