个人技术分享

算法提高之货币系统

• 核心思想：背包 + 贪心

  • 贪心思路：将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);  //清空f
            sort(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;
        }
    }