我其实真没发现这是个背包问题

题目

题目描述：
在网友的国度***有n种不同面额的货币，第i种货币的面额为a[i]，你可以假设每一种货币都有无穷多张。
为了方便，我们把货币种数为n、面额数组为a[1..n]的货币系统记作(n,a)。
在一个完善的货币系统中，每一个非负整数的金额x 都应该可以被表示出，即对每一个非负整数x，都存在n个非负整数t[i] 满足a[i] x t[i] 的和为x。
然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额x不能被该货币系统表示出。例如在货币系统n=3, a=[2,5,9]中，金额1,3就无法被表示出来。
两个货币系统(n,a)和(m,b)是等价的，当且仅当对于任意非负整数x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统(m,b)，满足(m,b) 与原来的货币系统(n,a)等价。
且m尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的m。

输入描述：
输入的第一行包含一个整数T,表示数据组数。接下来按照如下格式分别给出T组数据。
每组数据的第一行包含一个正整数n。接下来一行包含n个由空格隔开的正整数a[i]。

输出描述：
输出文件共T行, 对于每组数据, 输出一行一个正整数, 表示所有与(n, a)等价的货币系统(m, b)中, 最小的m。

解析

知识点

  1. 这道题其实就是一个背包dp，完全背包问题。
  2. 虽然我一开始非常的sa，以为这是单纯的倍数筛选，或者是筛选素因子。

看题目

  1. 那我们首先来看题目，这么长的题目看一眼就心肌梗塞，我们就一句话总结一下。
  2. 我们有一堆数，从这堆数中选出最少的数：组合这些数（相加）可以表示，原来数组可以表示的所有数，并且表示的数完全一样。

算法讲解

  1. 也就是说我们要选出这里面必不可少的一些数，这些数可以表示所有的数。
  2. 所以这里我们对于每个可以删除的数来说，这个数一定可以被一或多个比自己小的数用加法表示出来。
  3. 这不就是我们的完全背包吗？（完全背包等下看下面哦）
  4. 完全背包可以判断一个数到底能不能被其他的数表示。

背包dp-之-完全背包

  1. 背包问题最基本就是，给你一些东西，让你装这个包。完全背包就是判断：怎么能把这个包装满。
  2. 首先既然是dp，就少不了这句话：dp最重要的就是递推和dp数组的含义。
  3. 首先我们来讲dp数组的含义，在这里呢，dp数组只是表示某一个数能不能被表示（被装满）而已。
  4. 然后递推呢？递推要利用到背包方式计算（看下面）。
  5. 我用这道题的背包来解释一下背包问题的基本操作：——————————skr——————————
  6. 我们有三个数：3,10,19。我们很清楚的知道，10和3可以变成19。但是电脑要怎么知道呢？
  7. 首先我们知道3和10的倍数分别为：（3 6 12 15、10 20 30 40）这些都不能有。 然后判断10与3可以组成的数了。
  8. 我们判断，10和9也就可以变成19，而9可以由3得来。我们就是这样得到的答案。（详细看下面）

算法操作

  1. 那这个背包我们详细怎么操作呢？
  2. 我们的答案毫无疑问就是：总数减去删掉的数。所以我们先用一个ans变量初始化为n。
  3. 首先我们最小的数是不可能被别人表示的。
  4. 然后第二小的数，判断一下能不能被最小的表示。能表示就删掉这个数。
  5. 接下来第三小，就要判断能不能被前两个数表示（说到这里你应该就知道要排序了吧）。
  6. 以此类推，前面只需要从小到大遍历每个数，后面的判断就要靠完全背包dp了。（我们下面的栗子均是：3，10，19）
  7. 我们这个dp最重要的就是，判断一个数，能不能被一个比自己小a[i]的数表示出来（a[i]是啥，就是数组其中的一个数呀）。
  8. 栗子：我们要判断13能不能被表示，我们先判断加数为3的时候，这时候13 - 10（也就是比自己小a[i]的数）是3，可以表示（因为数组里面有10嘛）： 
    for (int i = 1; i <= n; i++)//这里循环遍历每一个数的情况
    for (int j = info[i]; j <= info[n]; j++)//这里循环判断每一个加数的情况
        dp[j] |= dp[j - info[i]];
//我们直接用info[i]循环到info[n]，这样就可以讲每个数预处理好。
//栗子：我们先处理好了倍数为3的所有数，然后处理好了10的倍数与10与3的各种之和
//能得到之和的原因同上，我们在判断13的时候，13-10=3，3可以，所以13也可以，19同理
    这里看一下代码有助于理解。

打代码

  1. 那我们就是先输入数据。
  2. 然后排序。
  3. 接下来遍历，并进行完全背包统计。
  4. 看我全代码~

AC代码 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e6 + 7;
int info[MAX];
bool dp[MAX];
//全局变量区

int main() {
    IOS;
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        for (int i = 1; i <= n; i++) cin >> info[i];
        sort(info + 1, info + 1 + n);
        memset(dp, 0, sizeof dp);
        dp[0] = 1;
        int ans = n;
        for (int i = 1; i <= n; i++) {
            if (dp[info[i]]) {
                ans--;
                continue;
            }
            for (int j = info[i]; j <= info[n]; j++)
                dp[j] |= dp[j - info[i]];
        }
        cout << ans << endl;
    }
    return 0;
}
//函数区