状态表示

f[i][j]表示前i个数中**可以组合为j**的方案个数；

状态转移方程

不选当前数 ：f[i][j]=f[i-1][j];

选择当前数 ：f[i][j]=f[i-1][j-w[i]]

滚动数组优化

f[j]+=f[j-w[i]]

C++代码

#include<iostream>
using namespace std;
const int N=110, M=1010;
int f[M], w[N];
int main()
{
    int n,m;
    cin >> n >> m;

    for(int i = 0; i < n; i ++) cin >> w[i];
    f[0] = 1;

    for(int i = 0; i < n; i ++)
        for(int j = m; j >= w[i]; j --)
            f[j] += f[j - w[i]];

    cout << f[m] << endl;

    return 0;
}