货币系统

https://ac.nowcoder.com/acm/problem/21228
题意：
有n种货币，每种货币数量无限，问能否删掉几种货币，使得原来能组成的数现在仍能组成。

分析：

想要去掉某种硬币，说明它可以被一种或多种面值比它小的货币所组成，一个或多个的和能组成某一个数，明显的背包问题，而且每个类型的货币数量无限，因此这题是一个完全背包问题。
由于每个货币只能由面值比它小的共同组成，所以我们应该先对给定货币面额进行正序排序，然后一个个判断拿还是不拿，如果发现当前面额能被组成，我们直接不管即可，如果发现不能组成，则进行状态转移把它范围内能组成的所有数标记一下即可。
状态转移方程为：dp[j] = dp[j] | dp[j-a[i]]

代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<set>
using namespace std;
typedef long long ll;
int i,j,cnt,n,k,t,b,m,x,ans;
using namespace std;
int a[105],dp[25005];
int main()
{
    scanf("%d",&t);
    while(t--){
        ans=0;
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        dp[0]=1;
        for(i=0;i<n;i++){
            if(!dp[a[i]])   ans++;//无法组成放进去
            else   continue;//能组成不管了
            for(j=a[i];j<=25000;j++){
                dp[j]|=dp[j-a[i]];//dp[j]由dp[j-a[i]]转移过来的
            }
        }
        printf("%d\n",ans);
    }
}