题目描述
作为 A 公司的职员,最盼望的日子就是每月的 8
号了,因为这一天是发工资的日子,养家糊口就靠它了。
但是对于公司财务处的工作人员来说,这一天则是很忙碌的一天,财务处的小胡最近就在考虑一个问题:
如果每个员工的工资额都知道,最少需要准备多少张人民币,才能在给每位职员发工资的时候都不用老师找零呢?
这里假设员工的工资都是正整数,单位元,人民币一共有 100元、50元、10元、5元、2元和 1元六种。
输入格式
输入包含多组测试数据。
每组数据第一行包含整数 n,表示员工数量。
第二行包含 n个整数,表示每个员工的应发工资。
输出格式
每组数据输出一行结果,表示最少需要准备的人名币张数。
数据范围
1≤n≤100,工资范围 [1,5000],输入最多包含 100组数据。
样例
输入样例:
3
1 2 3
2
1 2
输出样例:
4
2
算法1
(完全背包)
先用完全背包的思想离线算出获得1-5000所有金额的结果然后根据输入累加即可
时间复杂度
$O(n)$
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n;
int f[5005];
int v[] = {0,1,2,5,10,50,100};
int main()
{
memset(f,0x3f, sizeof f);
f[0]=0;
for(int i =1;i<=6;++i)
{
for(int j = v[i];j<=5003;++j)
{
f[j] = min(f[j],f[j-v[i]]+1);
}
}
while(cin>>n)
{
int ans = 0;
for(int i =1;i<=n;++i)
{
int tmp;
cin>>tmp;
ans += f[tmp];
}
cout<<ans<<endl;
}
return 0;
}