背包问题：货币系统

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();//表示数据组数
        int ans=0;
        for(int i=0;i<T;i++){
            int n = sc.nextInt();//n种不同面额的货币
            int[] a = new int[n];//货币面额数组
            for(int j=0;j<n;j++){
                a[j] = sc.nextInt();
            }
            Arrays.sort(a);
            //将面额数组中能被其他面额表示出来的删掉，剩下的个数即为答案
            //背包问题：a[1..i-1]能否拼出a[i]
            int count = huoBiXiTongII(n,a[n-1],a);
            System.out.println(count);
        }
    }
    public static int huoBiXiTongII(int n,int m,int[] a){
        //背包问题：n个物品，m容量，ai可用多次，求有多少种组合加起来是m
        //f[i]表示有多少种组合能拼出容量i
        int[] f = new int[m+1];
        f[0]=1;//有1种组合能拼出0（什么都不选）,f[1]=...=f[m]=0
        int i,j;
        for(i=1;i<=m;++i){
            for(j=0;j<n;j++){
                //如果i<a[j]，则对应的f[i-a[j]]不加入f[i]
                if(i>=a[j]){
                    f[i] += f[i-a[j]];
                }
            }
        }
        int count = 0;
        for(i=0;i<a.length;i++){
            //面额只有一种组成方式，即不能被其他面额表示出
            if(f[a[i]] == 1){
                ++count;
            }
        }
        return count;
    }
}