算法分析

若两个货币系统等价，有如下性质

• 性质1：a1,a2,...,an一定都可以被表示出来

• 性质2：在最优解中,b1,b2,...bm一定都是从a1,a2,...,an中选择的

• 性质3：b1,b2,...,bm一定不能被其他bi表示出来

步骤
由于数据中不存在负数，将a[]数组从小到大排序

• (1)若ai能被a0~a(i-1)表示出来，则一定不选

• (2)若ai不能被能被a0~a(i-1)表示出来，则一定选

时间复杂度 $O(nm)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 110;
    static int M = 25010;
    static int[] a = new int[N];
    static int[] f = new int[M];
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine().trim());
        while(T -- > 0)
        {
            int n = Integer.parseInt(reader.readLine().trim());
            String[] s1 = reader.readLine().split(" ");
            for(int i = 0;i < n;i++) a[i] = Integer.parseInt(s1[i]);
            Arrays.sort(a,0,n);
            Arrays.fill(f, 0);
            f[0] = 1;
            int res = 0,m = a[n - 1];
            for(int i = 0;i < n;i++)
            {
                if(f[a[i]] == 0) res ++;//凑不出来一定要
                for(int j = a[i];j <= m;j++)
                {
                    f[j] = f[j] + f[j - a[i]];
                }
            }
            System.out.println(res);
        }
    }
}