题目描述
给你一个货币系统,让你简化一下货币系统,使得能表示出来的价钱相同,求货币的最小种类值。
样例
2
4
3 19 10 6
5
11 29 13 19 17
结果
5
2
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110, M = 25010;
int n;
int a[N];
int f[M];
//把货币a[i]看成背包的体积容量,看看0~i-1种有木有把a[i]填满
//有的话货币a[i]就是可替代的
int main()
{
int T;
cin >> T;
while(T --)
{
cin >> n;
for(int i = 0; i < n; i ++)
cin >> a[i];
//排序从小到大,后面依次循环(大的货币可能由小的货币组成)
sort(a, a + n);
int m = a[n - 1];
//多组数据,每次要清零
memset(f, 0, sizeof f);
//f[0][0]简化过来的,表示前0个货币可以组成第零个货币的数量
f[0] = 1;
int res = 0;//记录还剩多少种货币
for(int i = 0; i < n ; i ++)
{
//如果遍历到该货币还是不能被其他货币表示,就是必须留下来的
if(!f[a[i]]) res ++;
for(int j = a[i]; j <= m; j ++)
f[j] += f[j - a[i]];//不能等于,会后面等于零的覆盖了的只能是加
}
cout << res << endl;
}
return 0;
}