#动态规划 #完全背包

题意

• 给定一个n种面值组成的货币系统，如果其中某一个面值可以由系统中的其它货币表示就认为这个面值是冗余的
• 求出这个货币系统去除冗余后最少有几种面值

思路

• 按照题意完全背包即可
• 注意判断一个货币是否冗余，是在使用它之前判断是否已经被表示

代码

#include<bits/stdc++.h>

using namespace std;

/**
 * 对于一个货币系统尝试简化它，其实就是从已知的种类中尝试删掉几个
 * 可以转化为一个完全背包，背包的容积为最大的面值
 * 尝试用小的货币去表示大的货币，如果可以表示，就删除
 */
int f[25500];
int a[200];
int cmp(int a,int b){
    return a<b;
}
int main(){
    int t;
    cin >> t;
    while(t--){
        memset(f,0,sizeof(f));
        memset(a,0,sizeof(a));
        int n;
        cin >> n;
        for(int i=1;i<=n;i++){
            cin >> a[i];
        }
        sort(a+1,a+n+1,cmp);
        f[0]=1;
        int ans=0;
        for(int i=1;i<=n;i++){
            if(f[a[i]]==1) ans++;
            for(int j=a[i];j<=a[n];j++){
                f[j]|=f[j-a[i]];
            }
        }
        cout << n-ans << endl;
    }
    return 0;
}