【正经题解】背包方案总数

这个问题是一个典型的背包问题，可以使用动态规划来解决。定义一个二维数组 $dp$ ，其中 $dp$ [ $i$ ][ $j$ ] 表示前 $i$ 个物品放入容量为 $j$ 的背包的方案数。则动态规划的状态转移方程为：
$dp$ [ $i$ ][ $j$ ] $=$ $dp$ [ $i-1$ ][ $j$ ] $+$ $dp$ [ $i-1$ ][ $j-w$ [ $i$ ]]

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int w[100];
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }

    // 初始化动态规划数组
    int dp[101][1001] = {0};
    
    // 边界条件：背包容量为0时，方案数为1
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 1;
    }

    // 动态规划过程
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // 不选第 i 个物品的方案数
            dp[i][j] += dp[i-1][j];
            // 选第 i 个物品的方案数
            if (j >= w[i]) {
                dp[i][j] += dp[i-1][j-w[i]];
            }
        }
    }

    // 输出结果
    cout << dp[n][m] << endl;

    return 0;
}