题目描述
艾伦是一个非常富有的人,他在银行存有n元钱,现在由于某些私人原因,他要将钱全部取出用于急用。
已知银行的钞票共分1, 5, 10, 20, 100这5种面值。
出于携带方便的考虑,艾伦希望组成这n元钱的钞票张数尽可能少。
请问在给定n的情况下,组成n元钱的钞票张数最少是多少。
样例
输入
125
输出
3
分析
由于是面额较大的钞票的是较小的整数倍
或者说面额较小的是较大的因子
所以贪心
C 代码
#include<stdio.h>
int a[5] = {100, 20, 10, 5, 1};
int main()
{
int i, n, ans = 0;
scanf("%d", &n);
for(int i = 0; i < 5; i ++)
{
ans += n / a[i];
n %= a[i];
}
printf("%d", ans);
return 0;
}
%%%
如果不是整数倍呢?
如果是整数倍,贪心是对的,如果不是,贪心就不一定对了,大概可以用完全背包