题目链接 AcWing 1021.货币系统
相似题目 AcWing 1023.买书
完全背包问题
二维版
f[i][j] 表示 只从前i种货币选组成面值为j的所有方案的集合 的总数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 20, M = 3010;
LL f[N][M];
int n, m;
int v;
int main()
{
cin >> n >> m;
f[0][0] = 1;
for(int i = 1; i <= n; i ++)
{
cin >> v;
for(int j = 0; j <= m; j ++)
{
f[i][j] += f[i - 1][j];
if(j >= v) f[i][j] += f[i][j - v];
}
}
cout << f[n][m] << endl;
return 0;
}
一维版
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 20, M = 3010;
LL f[M];
int n, m;
int v;
int main()
{
cin >> n >> m;
f[0] = 1;
for(int i = 1; i <= n; i ++)
{
cin >> v;
for(int j = v; j <= m; j ++)
{
f[j] += f[j - v];
}
}
cout << f[m] << endl;
return 0;
}