532 货币系统（完全背包问题）

电玩女神 2022-09-11 05:27 134阅读 0赞

**1. 问题描述：**

在网友的国度中共有n种不同面额的货币，第i种货币的面额为a\[i\]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为n、面额数组为a\[1..n\] 的货币系统记作(n，a)。在一个完善的货币系统中，每一个非负整数的金额x都应该可以被表示出，即对每一个非负整数x，都存在n个非负整数 t\[i\]满足a\[i\]×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 ≤ n ≤ 100，  
1≤ a\[i\] ≤ 25000，  
1 ≤ T ≤ 20

**输入样例：**

2  
4  
3 19 10 6  
5  
11 29 13 19 17

**输出样例：**

2  
5  
来源：[https://www.acwing.com/problem/content/description/534/][https_www.acwing.com_problem_content_description_534]

**2. 思路分析：**

对于NOIP的大部分题目都是先要挖掘一下题目隐藏的信息或者对应的数学性质，通过这些隐藏的信息或者数学性质来简化题目，使得可以使用比较简便的方法求解。分析题目可以知道从题目中挖掘到的有三个重要的性质：

*  a1，a2，...an一定可以被表示出来
 *  在最优解中b1，b2，...bm都是从a1，a2...an中选择出来的
 *  b1，b2，...bm一定不能够被其他的bi表示出来

第二条的信息对于解决这道题目来说非常关键，因为b1，b2，...bm限制了在a1，a2，...an中选择所以我们将一个庞大的解空间限制在了n个数字范围之内这样对于当前的问题就有求解的思路了：对于ai = ti \* bi，当bi不属于ai中的数字的时候那么bi一定是可以由ai中的某些数字表示出来，所以最终bi可以由b中的数字表示出来的，也即可以去除掉当前的数字bi，所以最优解中的b1，b2，...bm都是从a1，a2，a3中选择出来的，有了这个性质之后我们就可以通过逐个判断当前的a\[i\]是否可以由其他的a\[j\]表示出来，因为a\[i\] >= 1所以可以先对数组a从小到大排序，然后依次检查每一个a\[i\]是否可以由之前的a\[0\] ~ a\[i - 1\]的数字表示出来（每一个a\[i\]可以使用无限次），这样就将问题转化为了**完全背包问题**了。

**3. 代码如下：**

if __name__ == '__main__':
        # T为测试的组数
        T = int(input())
        for i in range(T):
            n = int(input())
            a = list(map(int, input().split()))
            # 先排序, 然后判断每一个a[i]是否可以由之前的1~a[i - 1]构成, a[0]~a[i-1]可以选择无线个
            a.sort()
            res = 0
            m = a[n - 1]
            dp = [0] * (m + 1)
            dp[0] = 1
            for j in range(n):
                # 判断当前的a[j]是否可以由之前的a[0] ~ a[j - 1]表示出来如果可以表示出来那么对应的结果肯定是大于0的, dp[j]表示体积为j的时候的方案数目
                if dp[a[j]] == 0: res += 1
                for k in range(a[j], m + 1):
                    dp[k] += dp[k - a[j]]
            print(res)

[https_www.acwing.com_problem_content_description_534]: https://www.acwing.com/problem/content/description/534/