最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

定义一个 货币系统 $(n, a)$：一共有 $n$ 种货币，每种货币对应面值为 $a_i$

每种货币可以使用 任意多个，进行线性组合：

$$ k = x_1a_1 + x_2a_2 + \cdots + x_na_n，其中 x_i \in Z_0~~i=1,2,\cdots $$

$k$ 为该 货币系统 $(n, a)$ 能够 线性表出 的数值

【注】本题的 线性表出 对于 系数的要求 和 线性代数 中的 线性表出 是不一样的

本题的系数必须是 非负整数

定义：
$$ (n, a) 和 (m, b) 等价 \Leftrightarrow \forall k \in Z^+， \begin{cases} k如果能被a线性表出，则k也能被b线性表出\\\ k如果不能被a线性表出，则k也不能被b线性表出 \end{cases} $$

现给定 货币系统 $(n, a)$，求一个 等价 的 货币系统 $(m, b)$ ，要求 $m$ 尽可能最小

分析

$n$ 种货币，每种货币可以使用 无穷多个

通过这些信息，我们可以初步识别该题目是一个 完全背包 的变种题目

接着我们需要挖掘一下题目里的性质：

学过 线性代数 的同学可以无视这一部分，跳到下面的分割线继续看

研究 货币系统 $(n, a)$ ，如果存在 $a_j$ 可以被 $a$ 中其他的向量 线性表出：

$$ a_j = \sum_{i\ne j} c_ia_i $$

则 $a_j$ 在这个货币系统中是 无效的 (所有线性表示中需要用到$a_j$的项，都可以用 $\sum_{i\ne j} c_ia_i$ 代替)

因此，我们需要求出 货币系统 $(n, a)$ 的 最大无关向量组，即任意 $a_i$ 都不能被其他向量 线性表出

如何求向量组 $(a_1,a_2,\cdots,a_n)$ 的 最大无关向量组

我们可以利用到 数论 中 埃式筛法 的思想：

对于一个 无效的 元素 $a_i$，他只会被 小于 他的元素的 线性组合 表出，满足该要求的 $a_i$ 就要被 筛掉

所以我们要先 排序

而我们在做 完全背包 的时候，需要求出所有恰好能被前 $i$ 个物品选出的体积的方案

即就是在 完全背包 求方案数的过程中，统计那些 初始不能被满足 的物品体积 个数

这就是我们在 AcWing 1021. 货币系统 中所使用的 DP模型

那一题我们求解的是方案数，这题稍微改一下，改成这种方案能否被满足即可，具体如下

闫氏DP分析法

再具体一点的代码实现，我会在代码的 注释 中再具体解释

Code

时间复杂度：$O(n\times m)$

空间复杂度：$O(m)$

其中 $m$ 是最大物品的体积

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//这题是一道线性代数问题
//求解一个向量组的秩(最大无关向量组的向量个数)
//但是代码写起来就是一个模拟筛的过程
//从小到大，先查看当前数有没有被晒掉，
//1)如果没有就把它加入到最大无关向量组中，并把他以及他和此前的硬币的线性组合都筛掉
//2)如果有就不理会
//即就是在完全背包求方案数的过程中，统计那些初始没有方案数的物品
//这样就变成一个完全背包问题了

const int N = 110, M = 25010;
int n;
int v[N];
bool f[M];

int main()
{
    int T = 1;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        for (int i = 1; i <= n; ++ i) cin >> v[i];
        sort(v + 1, v + n + 1);//排序的原因见之前的分析

        //我们只需统计所有物品的体积是否能被其他的线性表出
        //因此背包的体积只需设置为最大的物品体积即可
        //res用来记录最大无关向量组的个数
        int m = v[n], res = 0;
        memset(f, 0, sizeof f);
        f[0] = true;    //状态的初值
        for (int i = 1; i <= n; ++ i)
        {
            //如果当前物品体积被之前的物品组合线性筛掉了，则它是无效的
            if (f[v[i]]) continue;
            //如果没有被筛掉，则把它加入最大无关向量组
            res ++ ;
            //筛掉当前最大无关向量组能线性表示的体积
            for (int j = v[i]; j <= m; ++ j)
            {
                f[j] |= f[j - v[i]];
            }
        }
        //输出最大无关向量组的向量个数
        cout << res << endl;
    }
    return 0;
}