题解 | 神奇的口袋

#include <bits/stdc++.h>
#include <cstring>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        int dp[41];
        memset(dp, 0, sizeof(dp));
        dp[0]=1;
        for(int i=0;i<n;i++){
            int a;
            cin>>a;
            for(int j =40;j>=a;j--){
                dp[j]=dp[j]+dp[j-a];
            }
        }
        cout<<dp[40]<<endl;
    }
}

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

int main() {
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }

        // 定义dp数组，dp[i][j]表示前i个物品中，总和为j的方案数
        int dp[n + 1][41];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1; // 初始化：选0个物品，总和为0时方案数为1

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 40; j++) {
                // 不选第i个物品
                dp[i][j] = dp[i - 1][j];
                // 选第i个物品（保证不越界）
                if (j >= nums[i - 1]) {
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
        }

        cout << dp[n][40] << endl; // 输出从n个物品中选，总和为40的方案数
    }
}

01背包问题，直接写优化版本了，本质上逻辑是一样的，我们需要求组合，也就是在背包问题的逻辑下进行修正，修正为，当前背包大小下，选取物品的方案数，对于0，我们认为没有物品可选，也是一种方案，第一个解法是优化版本，如果看不懂，直接看第二个即可