1371.货币系统
| 1371. 货币系统 - AcWing题库 |
|---|
| 难度：简单 |
| 时/空限制：1s / 64MB |
| 总通过数：7096 |
| 总尝试数：12581 |
| 来源： usaco training 2.3 |
| 算法标签 DP背包问题 |
题目内容
给定 V 种货币（单位：元），每种货币使用的次数不限。
不同种类的货币，面值可能是相同的。
现在，要你用这 V 种货币凑出 N 元钱，请问共有多少种不同的凑法。
输入格式
第一行包含两个整数 V 和 N。
接下来的若干行，将一共输入 V 个整数，每个整数表示一种货币的面值。
输出格式
输出一个整数，表示所求总方案数。
数据范围
1≤V≤25,
1≤N≤10000
答案保证在long long范围内。
输入样例：
3 10
1 2 5
输出样例：
10
题目解析
V种货币，每种货币的使用次数是不限的
不同的货币，面值可能是相同的也可能是不同的
要用V种货币凑出N元钱，问有多少种不同的凑法
输入若干行，总共输入V个数，不一定每行一个数，也不一定只有一行
最多有25种货币
总钱数最大是10000
非常经典的完全背包问题
把总钱数N看成背包容量
把每种货币看成是一个物品
每种物品可以用无限个
如果想装满背包的话，一共有多少种不同的方案
时间复杂度是N*V，25万
如何分析完全背包问题
从集合角度来分析
-
状态表示
背包问题可以用一维来写，分析的时候最好用二维来分析f[i][j]
i表示物品，j表示当前的背包容量
- 当前状态表现的是哪个集合
表示只用前i种货币，且总钱数是j的所有方案的集合 - 存的是集合的哪个属性
问的是方案数，所以属性就是集合当中的元素数量
只要把每一个状态都求出来，答案就是f[V][N]
-
状态计算
集合的划分
求这个集合的元素数量的话，一般是先将这个集合分成若干个子集，分别求每一个子集的元素数，再相加，就可以了
划分的时候一般是找最后一个不同点，也就是第i种货币用的数量
用第i种货币用的数量将集合分成若干类
- 第一类是第i种货币用0个
- 第二类是用1个
- 第三类是用2个
- 以此类推
这种划分方案是不重不漏的
每一种方案可以依据第i种货币的数量一定属于且仅属于某一个子集
因此要求整个方案的方案数的话，只要分别求每个子集的方案数，再相加就可以了
如何求每一个子集的方案数
-
先看一下第一个子集的方案数，从具体含义来看怎么求
从1到i中选，且总金额是j的所有方案的集合，并且第i种货币选0个，等价于从1~i-1中选，总价值是j
根据状态表示，它恰好就是f[i-1][j] -
第二个子集的方案数
从1到i中选，总钱数是j，并且第i种货币用了1张，的所有方案的集合
前面随便选，最后一个都是只包含1个第i种货币
变化的部分就是前面，方案数就取决于前面可以变化出多少种
前面可以变化出多少种，要看前面变化的含义是什么
用1~i-1，凑出来
j
−
v
i
j - v_{i}
j−vi，的所有方案的集合
每一个前面的集合里面的方案加上一张
v
i
v_{i}
vi，就可以构成这个子集的一个方案
根据状态的表示，恰好就是f[i-1][j - v]
- 同理下一个子集的方案数就是
f[i-1][j - 2 * v] - 以此类推
最终，f[i][j] = f[i-1][j] + f[i - 1][j - v] + f[i - 1][j - 2 * v]...
状态数量是货币数量乘总金额25万
每个货币最多会用1万次
整个的时间复杂度
2.5
∗
1
0
9
2.5*10^9
2.5∗109
需要优化
通过公式变形，给这个式子做化简
用同样的方式把f[i][j - v]展开，相当于换元法，用j-v换掉v
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
+
f
[
i
−
1
]
[
j
−
v
]
+
f
[
i
−
1
]
[
j
−
2
v
]
…
f
[
i
]
[
j
−
v
]
=
f
[
i
−
1
]
[
j
−
v
]
+
f
[
i
−
1
]
[
j
−
2
v
]
+
f
[
i
−
1
]
[
j
−
3
v
]
…
\begin{array}{} f[i][j] = f[i-1][j] + f[i - 1][j - v] + f[i - 1][j - 2v]\dots \\ f[i][j-v]=f[i-1][j-v]+f[i-1][j-2v]+f[i-1][j-3v]\dots \end{array}
f[i][j]=f[i−1][j]+f[i−1][j−v]+f[i−1][j−2v]…f[i][j−v]=f[i−1][j−v]+f[i−1][j−2v]+f[i−1][j−3v]…
对比一下两个式子的后半部分，发现完全一样
所以第一个式子的后半部分其实就是
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
+
f
[
i
]
[
j
−
v
]
f[i][j] = f[i-1][j]+f[i][j-v]
f[i][j]=f[i−1][j]+f[i][j−v]
这样计算每个状态的时候就不需要循环10000次了，时间复杂度变为25万，可以过了
代码
二维空间写法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
//N表示货币数量，M表示背包容量
const int N = 30, M = 10010;
int n, m;
int v[N]; //v表示每一个货币的面值
LL f[N][M]; //f是状态数
int main()
{
scanf("%d%d", &n, &m);
//先读入每一种货币的面额
for (int i = 1; i <= n; i ++) scanf("%d", &v[i]);
//定义初始，一张货币也没有，也是一种方案
f[0][0] = 1;
//枚举一下所有的状态
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= m; j ++)
{
//左边的状态一定存在
f[i][j] = f[i - 1][j];
//后面的状态不一定存在，当j小于v的时候不存在
if (j >= v[i]) f[i][j] += f[i][j - v[i]];
}
printf("%lld\n", f[n][m]);
return 0;
}
优化空间的写法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
//N表示货币数量，M表示背包容量
const int N = 30, M = 10010;
int n, m;
int v[N]; //v表示每一个货币的面值
LL f[M]; //f是状态数
int main()
{
scanf("%d%d", &n, &m);
//先读入每一种货币的面额
for (int i = 1; i <= n; i ++) scanf("%d", &v[i]);
//定义初始，一张货币也没有，也是一种方案
f[0] = 1;
//枚举一下所有的状态
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= m; j ++)
{
//左边的状态一定存在
//右边的j还没有更新过，就是上层循环的f[i-1][j]
//左边的j是第i层循环算的j，就是f[i][j]
f[j] = f[j];
//后面的状态不一定存在，当j小于v的时候不存在
if (j >= v[i])
//左边的j是当前算的j，就是f[i][j]
//由于是从小到大枚举的j，在算j的时候，j-v[i]已经在当前第i层循环算过了，所以右边这样写的话，用的就是第i层循环的j-v[i]
f[j] += f[j - v[i]];
}
printf("%lld\n", f[m]);
return 0;
}
再优化
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
//N表示货币数量，M表示背包容量
const int N = 30, M = 10010;
int n, m;
int v[N]; //v表示每一个货币的面值
LL f[M]; //f是状态数
int main()
{
scanf("%d%d", &n, &m);
//先读入每一种货币的面额
for (int i = 1; i <= n; i ++) scanf("%d", &v[i]);
//定义初始，一张货币也没有，也是一种方案
f[0] = 1;
//枚举一下所有的状态
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= m; j ++)
{
f[j] = f[j]; //这句话是恒等式，可以删掉
if (j >= v[i])
//当j小于v[i]的时候，循环会直接跳过，可以让j直接从v[i]开始枚举
f[j] += f[j - v[i]];
}
printf("%lld\n", f[m]);
return 0;
}
变成
for (int i = 1; i <= n; i ++)
for (int j = v[i]; j <= m; j ++)
f[j] += f[j - v[i]];
完全背包问题，直接改完是等价的
01背包问题改完不等价，需要倒过来循环