二维
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long i64;
typedef pair<int, int> PII;
int n, m;
const int N = 10010;
i64 f[30][N];
int w[30];
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> w[i];
f[0][0] = 1;
for (int i = 1; i <= n; i ++)
{
for (int j = 0; j <= m; j ++)
{
for (int k = 0; k * w[i] <= j; k ++)
{
f[i][j] += f[i - 1][j - k * w[i]];
}
}
}
cout << f[n][m] << "\n";
return 0;
}
一维
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long i64;
typedef pair<int, int> PII;
int n, m;
const int N = 10010;
i64 f[N];
int w[30];
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> w[i];
f[0] = 1;
for (int i = 1; i <= n; i ++)
{
for (int j = w[i]; j <= m; j ++)
{
f[j] += f[j -w[i]];
}
}
cout << f[m] << "\n";
return 0;
}