【每日一题】货币系统
货币系统
https://ac.nowcoder.com/acm/problem/21228
我其实真没发现这是个背包问题
题目描述：
每组数据的第一行包含一个正整数n。接下来一行包含n个由空格隔开的正整数a[i]。
题目
题目描述： 在网友的国度***有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。
解析
知识点
- 这道题其实就是一个背包dp，完全背包问题。
- 虽然我一开始非常的sa，以为这是单纯的倍数筛选，或者是筛选素因子。
看题目
- 那我们首先来看题目，这么长的题目看一眼就心肌梗塞，我们就一句话总结一下。
- 我们有一堆数，从这堆数中选出最少的数：组合这些数（相加）可以表示，原来数组可以表示的所有数，并且表示的数完全一样。
算法讲解
- 也就是说我们要选出这里面必不可少的一些数，这些数可以表示所有的数。
- 所以这里我们对于每个可以删除的数来说，这个数一定可以被一或多个比自己小的数用加法表示出来。
- 这不就是我们的完全背包吗？（完全背包等下看下面哦）
- 完全背包可以判断一个数到底能不能被其他的数表示。
背包dp-之-完全背包
- 背包问题最基本就是，给你一些东西，让你装这个包。完全背包就是判断：怎么能把这个包装满。
- 首先既然是dp，就少不了这句话：dp最重要的就是递推和dp数组的含义。
- 首先我们来讲dp数组的含义，在这里呢，dp数组只是表示某一个数能不能被表示（被装满）而已。
- 然后递推呢？递推要利用到背包方式计算（看下面）。
- 我用这道题的背包来解释一下背包问题的基本操作：——————————skr——————————
- 我们有三个数：3,10,19。我们很清楚的知道，10和3可以变成19。但是电脑要怎么知道呢？
- 首先我们知道3和10的倍数分别为：（3 6 12 15、10 20 30 40）这些都不能有。 然后判断10与3可以组成的数了。
- 我们判断，10和9也就可以变成19，而9可以由3得来。我们就是这样得到的答案。（详细看下面）
算法操作
- 那这个背包我们详细怎么操作呢？
- 我们的答案毫无疑问就是：总数减去删掉的数。所以我们先用一个ans变量初始化为n。
- 首先我们最小的数是不可能被别人表示的。
- 然后第二小的数，判断一下能不能被最小的表示。能表示就删掉这个数。
- 接下来第三小，就要判断能不能被前两个数表示（说到这里你应该就知道要排序了吧）。
- 以此类推，前面只需要从小到大遍历每个数，后面的判断就要靠完全背包dp了。（我们下面的栗子均是：3，10，19）
- 我们这个dp最重要的就是，判断一个数，能不能被一个比自己小a[i]的数表示出来（a[i]是啥，就是数组其中的一个数呀）。
- 栗子：我们要判断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同理
这里看一下代码有助于理解。
打代码
- 那我们就是先输入数据。
- 然后排序。
- 接下来遍历，并进行完全背包统计。
- 看我全代码~
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;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
