$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题是从给定的 $N$ 个数中选出一些数使得他们相加可以得到 $M$ ，每个数只能选一次，是经典的 01 背包问题，不是完全背包！！

求方案数的分析思路跟求最大最小值的分析思路一样

我们定义 $f[j]$ 所表示集合为：在前 $i$ 个数当中选择，体积之和恰好为 $j$ 的所有方案数，属性为所有方案数的总和

参考 01 背包的分析思路，有 $f[i][j]=f[i-1][j]+f[i-1][j-v]$ ，由于是求方案数，因此是将两种划分全部相加起来

转成一维便是 $f[j]+=f[j-v]$ ，并且由于是 01 北部，因此必须从后往前遍历

需要特别说明的是，这种求方案数的问题，对 $f[j]$ 数组是需要初始化的，一般是对下标为 0 的值进行初始化

在本题中，表示对前 $i$ 个数进行选择，加和为 0 的方案数为 1 ，即 $f[0]=1$

完整代码：

#include <iostream>

using namespace std;

const int N = 1e4 + 10;

int f[N];
int n, m;

int main()
{
    cin >> n >> m;
    f[0] = 1;//求方案数的问题，一般是在下标为0的位置进行初始化
    for(int i = 1; i <= n; i++)
    {
        int v;
        cin >> v;
        for(int j = m; j >= v; j--)
            f[j] += f[j - v];
    }
    cout << f[m] << endl;
    return 0;
}