KY59 神奇的口袋

01背包确定方案数量（板子）
ti

 #include<bits/stdc++.h>

 using namespace std;

int n;
int a[25];
int dp[45][45];

 int main()
 {
    cin>>n;
    for(int i = 1; i <= n; i ++ ){
        cin>>a[i];
    }
    //注意前i个物品凑体积为0的方案数都为1 
    for(int i = 0; i <= 20; i ++ ) dp[i][0] = 1;
    
    for(int i = 1; i <= n; i ++ ){  
        for(int j = 0; j <= 40; j ++ ){  
            if(j < a[i]) dp[i][j] = dp[i - 1][j];  //当第i个物品加不进去时 
            else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i]];  //当第i个物品能加进去时 
        }
    }
    cout<<dp[n][40]<<endl;
    return 0;
 }