【每日一题】5月27日 货币系统

题目大意：有n中货币，每种货币都有无限多个，问是否可以简化货币个数，使得能表示的数个数不变。

分析：容易想到货币中最小的面值肯定要留下，那么考虑第二小的货币是否可以去掉，如果第二小的货币是最小货币的倍数，那么就能去掉。那么考虑第i小的货币是否能够留下，那么我们是要查看已留下的货币能否表示当前的货币，那么这个就是一个多重背包问题。先将所有物品按照面值排序，然后从小到大枚举物品进行背包前判断改物品是否能被表示，如果可以那么这个物品就不拿， 否则进行背包。

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
typedef long long ll;
const int maxn=25005;

int t;
int a[105],n;
bool dp[maxn];


int main()
{
    cin>>t;
    while( t-- )
    {
        cin>>n;
        for( int i=1;i<=n;i++ ) cin>>a[i];
        sort(a+1,a+1+n);
        int ans=0,now=0;
        memset(dp,0,sizeof(dp));dp[0]=true;
        for( int i=1;i<=n;i++ )
        {
            if( !dp[a[i]] ) ans++;
            else continue;
            for( int j=a[i];j<=25000;j++ ) dp[j]|=dp[j-a[i]];
        }
        cout<<ans<<endl;
    }
}