算法提高之货币系统

• 核心思想：背包 + 贪心

  • 贪心思路：将a从小到大排序，因为a数组中数如果能用之前的数线性表示则它一定没用
    • 所以对每一个数 求其是否能用前i-1个数表示（背包求方案数）
    • 如果不能被其他数表示 就加入到b数组

•   #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 110,M = 25010;int f[M];int a[N];int n,m,T;int main(){cin>>T;while(T--){cin>>n;for(int i=0;i<n;i++) cin>>a[i];memset(f,0,sizeof f);  //清空fsort(a,a+n);int m = a[n-1];  //找最大值f[0] = 1;  //求方案数 初始化int res=0;for(int i=0;i<n;i++){if(!f[a[i]]) res++;  //不能被其他数线性表示 加入b数组for(int j=a[i];j<=m;j++)f[j] += f[j-a[i]];}cout<<res<<endl;}}