其实这道题目如果加上证明有蓝的
观察样例的解释，我们可以猜测一个结论：最终的货币面值一定由最初的货币面值的子集构成，而且没有选择的货币面值是可以被选择的货币面值线性表示的
所以我们马上就得到了一个DP算法，在考场上实在证不出来直接写就好了：
1、将\(a\)数组从小到大排序
2、最小的数必须要选，然后利用完全背包的思想，从\(a_i\)到最大值筛选一遍，将可以组成的打上标记
3、在判断后面的数字时，如果已经被标记过了，就不再选，没有被标记过就标记一下，再筛选一次数(即一次完全背包)
那么我们来详细证明一下这个结论
首先，一个很显然的地方，原来货币系统的最小面值一定要选择的，而且不可能选择比这个最小值还小的面值
然后利用数学归纳法从小到大考虑是否选择每个面值，假设我们已经选择了最终方案的货币面值，而且这些货币面值都是由原来货币系统的面值组成的，而且是线性无关的，现在再考虑是否选择面值\(k\)
如果\(k\)是原来货币系统的面值，如果\(k\)不能够被已经选择的面值线性表示那么肯定是要选择的，如果能够被线性表示那么肯定是不用选择的，这个比较显然
如果\(k\)不是原来货币系统的面值，如果能够被线性表示，那么肯定也是不用选择的，最难证明的其实是不能被线性表示的情况
这里我们用反证，假设最终的方案选了\(k\)，那么\(k\)一定不能被最终方案里比其小的面值线性表示，而最终货币系统与原货币系统等价的，所以\(k\)这个面值一定能够被原货币系统线性表示，也就是原货币系统中有未被最终货币系统选择的面值参与线性表示\(k\)，然而最终的货币系统不包含这些没被选择的面值，也就是说这些没被选择的面值可以被选择了的面值线性表示，这就可以推出\(k\)可以被选择了的面值线性表示，反证结束
标签：表示,系统,选择,线性,货币,面值 From： https://www.cnblogs.com/dingxingdi/p/17987173