$$\color{Red}{货币系统:完全背包求极大无关组}$$

我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

算法分析

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

性质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)表示出来，则一定选

极大无关组就是排序后，每次判断完全背包下，前i-1个物品能否正好组成v[i]的值，即用前i-1个物品表示第i个物品的方案数是否大于0，如果能表示说明此项多余,不能表示说明它是极大无关组的成员

时间复杂度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, M = 25010, n, T;
    static int[] v = new int[N];
    static int[][] f = new int[N][M];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        T = Integer.parseInt(s1[0]);
        while (T-- > 0) {
            String[] s2 = br.readLine().split(" ");
            n = Integer.parseInt(s2[0]);
            String []s3 = br.readLine().split(" ");
            for (int i = 1; i <= n; i++) {
                v[i] = Integer.parseInt(s3[i - 1]);
                Arrays.fill(f[i], 0);
            }
            Arrays.sort(v, 1, n+1);
            f[0][0] = 1;
            int res = 0, m = v[n];
            for (int i = 1; i <= n; i++) {
                /*
                /* 这里是理解题目的关键 每当遍历到一个新的v[i]
                * 若它可以被前i-1个数凑出来（完全背包的无限数量表示）
                * 则它可以作为极大线性无关组的元素存在
                * */
                if(f[i-1][v[i]] == 0) res++;
                for (int j = 0; j <= m; j++) {
                    //预防无法放下的情况
                    f[i][j] = f[i-1][j];
                    if(j >= v[i])
                        f[i][j] += f[i][j - v[i]];
                }
            }
            System.out.println(res);
        }
    }
}

java一维优化

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

public class Main {
    static int N = 110, M = 25010, n, T;
    static int[] v = new int[N];
    static int[] f = new int[M];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        T = Integer.parseInt(s1[0]);
        while (T-- > 0) {
            String[] s2 = br.readLine().split(" ");
            n = Integer.parseInt(s2[0]);
            String []s3 = br.readLine().split(" ");
            for (int i = 1; i <= n; i++) 
                v[i] = Integer.parseInt(s3[i - 1]);
            Arrays.fill(f, 0);
            Arrays.sort(v, 1, n+1);
            f[0] = 1;
            int res = 0, m = v[n];
            for (int i = 1; i <= n; i++) {
                /***
                * 这里是理解题目的关键 每当遍历到一个新的v[i]
                * 若它可以被前i-1个数凑出来（完全背包的无限数量表示）
                * 则它可以作为极大线性无关组的元素存在
                ***/
                if(f[v[i]] == 0) res++;
                for (int j = v[i]; j <= m; j++) 
                    f[j] += f[j - v[i]];
            }
            System.out.println(res);
        }
    }
}