题解 | 神奇的口袋

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<int>a(n+1,0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<int>f(41,0);
    f[0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=40;j>=a[i];j--){
            f[j] += f[j-a[i]];
        }
        //cout<<i<<"  "<<f[40]<<"\n";
    }
    cout<<f[40];
    return 0;
}

动态规划（01背包问题变种），数组a存物品，数组f存方案数，f[v]代表选取数组a中元素之和为v时的方案数，f[40]即为答案