思路

1. 排序货币面值a[0]~a[n-1]
2. 从小到大枚举货币面值, 如果a[i]不能被比他更小的面值线性表示(这里转化为完全背包问题求解), 则保留该面值res++
3. 判断货币面值是被要被保留f[a[i]]==0先于货币面值循环for(int j=a[i]; j<=a[n-1]; ++j)

c++ 货币系统: 完全背包问题

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

const int N=105;
const int M=25005;
int a[N];
int f[M];
int n,t;

int main(){
    // 完全背包问题, 当某面值货币不能被比其小面值货币线性组合表示, 该面值需要被选入集合中
    cin>>t;
    while(t--){
        memset(a, 0x00, sizeof a);
        memset(f, 0x00, sizeof f);
        cin>>n;
        for(int i=0; i<n; ++i) cin>>a[i];
        sort(a, a+n);
        f[0]=1;
        int res=0;
        for(int i=0; i<n; ++i){
            if(!f[a[i]]) res++;
            for(int j=a[i]; j<=a[n-1]; ++j)
                f[j]+=f[j-a[i]];
        }
        cout<<res<<endl;
    }

    return 0;
}

python

class Solution:
    def main(self, t:int):
        for _ in range(t):
            n=int(input())
            a=list(map(int, input().split()))
            a.sort(key=lambda x:x)
            f=[0 for _ in range(a[n-1]+1)]
            f[0]=1
            res=0
            for i in range(n):
                if not f[a[i]]: res+=1
                for j in range(a[i], a[n-1]+1):
                    f[j]+=f[j-a[i]]
            print(res)


if __name__ == '__main__':
    t = int(input())
    sol=Solution()
    sol.main(t)