货币系统（完全背包）

题目：

给你n个数的正整数集合。让你挑选最少的数，使两个集合等价。集合等价，即两个集合能表示的数的集合相同。

做法：

由于给的都是正整数。题目就是让我们求给定的n个数中，哪些数是不必要的。
所谓不必要，即某个数能被集合中的其他数表示。我们将集合a[]排序。若a[i]能被前i-1个数中的某个子集表示，则这个数就是不必要的。
想到这，不难发现这就是个完全背包。
做完全背包时，考虑到第i个数时，此时dp[]数组保存的恰是前i-1个数能表示的所有数。我们check一下此时dp[a[i]]的值。若为1说明a[i]容量的背包能被前i-1个数装满。即不必要。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 25000 + 7;
int a[N], dp[N];
int main(void){
    IOS;
    int T; cin >> T;
    while (T--){
        memset(dp, 0, sizeof dp);
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        sort(a+1, a+n+1);
        int mx = a[n];
        dp[0] = 1;
        int ans = n;
        for (int i = 1; i <= n; ++i){
            if (dp[a[i]]){
                ans--; continue;
            }
            for (int j = 1; j <= mx; ++j){
                if (j >= a[i]){
                    dp[j] |= dp[j-a[i]];
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}