f[i][j]状态表示：前i个物品，选择的物品总值恰好为j的所有情况和

状态计算：

不要a[i] : f[i - 1][j];
要a[i] : f[i - 1][j - a[i]]

f[i][j] = f[i - 1][j] + f[i - 1][j - a[i]]因为此题求的是方案数而非max或min。

代码实现：

# include <iostream>
using namespace std;

const int N = 110 , M = 10010;

int w[N];
// int f[N][M];  //二维

int f1[M];

int n,m;

int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d",&w[i]);
    }

    /*  // 二维
    f[0][0] = 1;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 0 ; j <= m ; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= w[i])
            {
                f[i][j] += f[i - 1][j - w[i]]; 
            }
        }
    }
    printf("%d\n",f[n][m]);
    */

    // 一维
    f1[0] = 1;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = m ; j >= w[i] ; j--)
        {
            f1[j] += f1[j - w[i]]; 
        }
    }
    printf("%d\n",f1[m]);
    return 0;
}