题解 | #神奇的口袋#

#include <bits/stdc++.h>
#define MAX 100
using namespace std;

int main() {
    int dp[MAX][MAX], v[MAX];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> v[i];
    memset(dp, 0, sizeof(dp));
//  for(int j = 1; j <= 40; j++)
//      dp[0][j] = 0;
    for (int i = 0; i <= n; i++) //前i个物品凑0体积都为1
        dp[i][0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 40; j++) {
            if (v[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = dp[i - 1][j - v[i - 1]] + dp[i -1][j]; //选择由 选当前 + 不选当前 组成
        }

    cout << dp[n][40];
}