经典完全背包问题。
二维做法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 30, M = 10010;
int n, m;
LL f[N][M]; //f[i][j]表示只用前i种货币,凑出j块钱的方法数
int main()
{
cin >> n >> m;
f[0][0] = 1; //状态初始化:0种货币凑0元为一种合法方案
for (int i = 1; i <= n; i ++ )
{
int v;
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>
using namespace std;
typedef long long LL;
const int N = 30, M = 1e4 + 10;
int n, m;
LL f[M];
int main()
{
cin >> n >> m;
f[0] = 1;
for (int i = 1; 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;
}