<---- 麻烦点一下旁边那个向上的三角
推销一下:
$\color{#00FF7F}{算法提高课 第一章 动态规划 全题解(正在完善)}$
题目描述
给定 $V$ 种货币(单位:元),每种货币使用的次数不限。
不同种类的货币,面值可能是相同的。
现在,要你用这 $V$ 种货币凑出 $N$ 元钱,请问共有多少种不同的凑法。
输入格式
第一行包含两个整数 $V$ 和 $N$。
接下来的若干行,将一共输入 $V$ 个整数,每个整数表示一种货币的面值。
输出格式
输出一个整数,表示所求总方案数。
数据范围
$1 \le V \le 25$,
$1 \le N \le 10000$
答案保证在long long
范围内。
输入样例:
3 10
1 2 5
输出样例:
10
题意简述
给定 $n$ 种面值的货币,求组成面值为 $m$ 的货币有多少种方案。
注意:
每种面值的货币可以重复使用
每种方案必须是组成的面值恰好等于$m$
求的是方案数量,不是最大价值
算法1
(二维动态规划) $O(n^3)$
这道题只要抽象好表述,就能很快与 AcWing 1023. 买书 一题对应,从而快速解决问题。
根据
组成面值为 $m$ 的货币
可以感受到,可以将 $m$ 抽象为背包容量。
那物品是什么呢,除了 $m$ 只剩下 $n$ 种面值的货币。
那我们将其抽象为物品体积,并将物品放入背包,求方案数。
整理:
- 组成面值为 $m$ 的货币 $\to$ 背包容量
- $n$ 种面值的货币 $\to$ 物品体积
求方案数量我们可以参考最初的 AcWing 278. 数字组合 01背包求方案数量问题。
注意到隐藏条件:货币有无数张。可以判断为完全背包求方案数量问题。
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 30,M = 10010;
int v[N];
long long f[N][M];
int main(){
int n,m;
scanf("%d%d",&n,&m);
f[0][0] = 1;
for(int i = 1;i <= n;i ++) scanf("%d",&v[i]);
for(int i = 1;i <= n;i ++){
for(int j = 0;j <= m;j ++){
for(int k = 0;v[i] * k <= j;k ++){
f[i][j] += f[i - 1][j - v[i] * k];
}
}
}
printf("%lld",f[n][m]);
return 0;
}
注意:
这里的 $f$ 数组会爆 $int$,所以要用$long \ long$
如果你是用 $printf$ 输出,记得是printf("%lld",f[n][m])
算法2
(一维数组DP) $O(n^2)$
这里我就只把最初和最后的代码放出来啦,其他方法可以看一下我买书那题的题解
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 30,M = 10010;
int v[N];
long long f[M];
int main(){
int n,m;
scanf("%d%d",&n,&m);
f[0] = 1;
for(int i = 1;i <= n;i ++) scanf("%d",&v[i]);
for(int i = 1;i <= n;i ++){
for(int j = v[i];j <= m;j ++){
f[j] += f[j - v[i]];
}
}
printf("%lld",f[m]);
return 0;
}
$$(共140行)$$