题目描述以及思路分析
V 种货币凑出 N 元钱, 每种货币使用的次数不限。
数据范围:
1≤V≤25,
1≤N≤10000
答案保证在long long范围内。
这里通过题目知道每种货币的使用次数不限,故这是一个完全背包问题. 故这里要用dp来分析这个问题。这里用y总的闫氏DP分析法:
从状态表示和状态计算这两个方面考虑,首先状态表示这是根据题目来分析的,其分为集合和属性两个, 集合是是指 i ~ j 表示的集合是什么,这里根据题目
来建立集合模型,故这里的集合表示的是 1 ~ i 种硬币中凑出j元的集合。 属性 指的是表示的这个集合表示的属性是什么,常见的属性为这个集合中的最大值/最小值/可行的个数.
状态计算主要是写出一个递归方程,根据给出的一个集合 f(i,j) 将这个大的集合再细分成小的集合。
| 集合 : 从1 ~ i 种硬币中选凑成j元方案的集合
|
|
|------------状态表示 -----| 属性 : 集合中的个数
|
|
|
DP
|
|
|
|
|------------状态计算 : 根据集合划分,将一个大集合划分为若干个子集,
设我们要求解f(i,j), 然后来尝试将其分为更小的集合
对集合f(i,j) , 这个集合我们可以把它先分为两部分, 一部分是 (1) 不包含第 i 种硬币的可行方案数,(2) 必包含第 i 种硬币的可行方案
|----------------(1) 不包含第 i 种硬币的可行方案数 f(i - 1, j);
|
|
f(i,j)
|
|----------------(2) 必包含第 i 种硬币的可行方案数 : 这里又分为第i个硬币包含1,2 ,3 ... , k(k最大 j / v 下取整, v为第i个硬币的面值)
故通过分解集合, 我们将f(i,j) 这个集合分为两部分, 但 (2) 这部分还是不怎么好表示, 故对(2) 接着分析
(2) 的总方案 包括有且只包含一个第i个硬币的,且第i个硬币的面值为v : 方案数为 f(i - 1, j - v); 这里由于必定包含一个第 i 个硬币, 所以其方案数等价于
用前 i - 1 种硬币 凑出 j - v (减去第i个硬币的面额) 的方案数, 同理只包含 2 个 第i个硬币的方案数为 f(i - 1, j - 2v); 故包含第i个硬币k个的方案数为
f(i - 1. j - [j / v] * v); 这里的 [j/v]表示的是下取整。 故 (2) 集合的总方案数为 = f(i - 1, j - v) + f(i - 1, j - 2v)+....+ f(i - 1. j - [j/v] * v);
故f(i,j) = (1) + (2)
= f(i - 1, j) + f(i - 1, j - v) + f(i - 1, j - 2v)+....+ f(i - 1. j - [j/v] * v);
这样计算 f(i,j) 就可以由前面的递归过来, 但这样表示还是不够简明,因为一般dp的递归方程都很短,故需要优化, 观察式子很像一个数列,故想到想消的做法
由上面的式子写出下面这个式子
f(i, j - v) = f(i - 1, j - v) + f(i - 1 , j - 2v) + … + f(i - 1, j - [j/v] * v); 可以看到 f(i, j - v) 就等于 f(i, j) 的(2)子集, 故用f(i, j - v)替换
故f(i, j) = f(i - 1, j) + f(i , j - v); 注意这个(2)部分有可能为空集,其不为空集的条件为 j >= v;
其实如果是这种背包问题的话,我们先是按照 01 背包的思路把一个集合划分为两个集合,一个表示不含i,一个表示必含i的,01背包的必含i的情况因为就一种,所以很好表示
但这里由于选的东西无限,故我们接着将第二部分进行再划分集合,分为必含第i个硬币1,2,3,4,....k个的情况。故这里刚开始的不如直接就按这样划分,不包含i个硬币的
方案就是必包含0个第i个硬币的方案,故依次类推,不用先分两个集合,再从另一个集合继续划分,虽然最后分析的结果是一样的,但明显不是直接一步到位。
故根据上面的思路推导出递推方程后 即可以开始写代码, 定义 一个 二维数组, 第一维表表示货币的种类, 第二伟表示所凑的钱数
#include<iostream>
using namespace std;
using LL = long long; // 注意题目有提示不超过long long 类型, 故这里的数组应该用long long 类型
constexpr int V = 35;
constexpr int N = 1e+4 + 10;
int v, n;
LL f[V][N];
auto main() -> int
{
cin >> v >> n;
for(int i = 0; i <= v; ++i) // 初始化递归条件, 这里主要是针对一些特判的情况,在真正开始递推之前先赋值
f[i][0] = 1; // 例如当所需要凑的钱数为 0 的情况下,此时只有一种方案,就是什么硬币的种类均为0, 故由于只有这一种可行方案,故赋值1
for(int i = 1; i <= v; ++i) // 外部的第一维由硬币的种类开始循环
{
int va; cin >> va; // 这里可以用 一个 一维数组来保存每个硬币的面值,但是由递归知道求一种情况的时候不需要用到之前硬币的面额,故不需要直接这里输入即可
for(int j = 1; j <= n; ++j) // 内部的第二维, 由所需钱数开始.
{
f[i][j] = f[i - 1][j]; // 递推方程的第1部分必定存在
if(j >= va) f[i][j] += f[i][j - va]; // 第二部分的成立有条件限制
}
}
cout << f[v][n] << endl; // 题目要求的答案,即从 1 ~ v 种硬币种选,凑出n元的可行方案数, 故这里直接输出 f[v][n];
return 0;
}
空间的优化, 一般的步骤都是先有一个正确的思路, dp就是在暴搜的基础上优化了时间,现在优化完时间再来优化空间 –》 转化为 1 维数组
首先为什么能优化成一维数组?
首先能优化为一维数组是有条件的,这跟题目所有求的有关系,因为题目只是要求输出个数,并没有要求具体的方案,然后我们的递归方程观察也可以发现当我们要求 f(i,j) 的时候
其实只用到了 f(i - 1, xx) 这一层 与 f( i - 2 , xxx) , f(i - 3, xxx) 并没有关系, 故我们这里直接先把上面的代码的第一维都去掉, 再去掉一些恒等式,和修改一些,代码代码如下
#include<iostream>
using namespace std;
using LL = long long; // 注意题目有提示不超过long long 类型, 故这里的数组应该用long long 类型
constexpr int V = 35;
constexpr int N = 1e+4 + 10;
int v, n;
LL f[N];
auto main() -> int
{
cin >> v >> n;
for(int i = 0; i <= v; ++i)
f[0] = 1; // 故这里直接去掉一个 for
for(int i = 1; i <= v; ++i)
{
int va; cin >> va;
for(int j = 1; j <= n; ++j) // 注意一下这层循环需不需从大到小循环, 这要观察下面的这个式子,由于下面的式子只有在 j > = va 才执行,而此时 f[j - va] 就是属于原本上一层的,故不需要
{
f[j] = f[j]; // 恒等式, 这里可以直接去掉
if(j >= va) f[j] += f[j - va]; // 由于只有 j >= va 才执行, 前面都没变, 故这里可以直接将for中的 j = 1 修改为 j = va; 然后再去掉这个if判断, 故修改后的代码如下所示
}
}
cout << f[v][n] << endl; // 题目要求的答案,即从 1 ~ v 种硬币种选,凑出n元的可行方案数, 故这里直接输出 f[v][n];
return 0;
}
优化后的代码
#include<iostream>
using namespace std;
using LL = long long;
constexpr int V = 35;
constexpr int N = 1e+4 + 10;
int v, n;
LL f[N];
auto main() -> int
{
cin >> v >> n;
f[0] = 1;
for(int i = 1; i <= v; ++i)
{
int va; cin >> va;
for(int j = va; j <= n; ++j)
f[j] += f[j - va];
}
cout << f[n] << endl;
return 0;
}
赞一个