题目描述
给定 $V$ 种不同面值的货币(单位:元),每种货币使用的次数不限。
现在,要你用这 $V$ 种货币凑出 $N$ 元钱,请问共有多少种不同的凑法。
输入格式
第一行包含两个整数 $V$ 和 $N$。
接下来的若干行,将一共输出 $V$ 个整数,每个整数表示一种货币的面值。
输出格式
输出一个整数,表示所求总方案数。
数据范围
$1≤V≤25$
$1≤N≤10000$
输入样例
3 10
1 2 5
输出样例
10
完全背包问题
完全背包问题(裸),和 AcWing 1365.子集的和 是非常类似的,不过它并不是可取无限次,集合中的每个数只可取一次,是一个 01 背包问题。
而 完全背包问题 和 01背包问题 的唯一不同就是体积的枚举顺序相反(从小到大 和 从大到小)。
C++ 代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 10010;
int n, m;
LL f[N];
int main() // 完全背包问题求解总方案数
{
cin >> n >> m;
f[0] = 1;
for (int i = 0; i < n; ++i) {
int v;
cin >> v;
for (int j = v; j <= m; ++j) {
f[j] += f[j - v];
}
}
cout << f[m] << endl;
return 0;
}
理解之后(虽说我还不怎么理解),模板还是得好好背的。