题解 | #神奇的口袋#

#include <iostream>
#include <vector>
using namespace std;

/**
* 递归实现，空间开销大，时间开销大
* 二维数组实现（动态规划），空间开销大，时间快
* 一维数组实现（动态规划），空间和时间开销都很小
**/

int commoditySelect(vector<int> vec, int n, int v);//挑选前n个物品，物品总体积为v

int main() {
    int n, temp;
    cin >> n;
    vector<int> commodity;
    for(int i = 1; i <= n; i++){
        cin >> temp;
        if(temp <= 40){//过滤40以上的数据
            commodity.push_back(temp);
        }
    }
    //二维数组实现
    vector<vector<int>> vec(n + 1, vector<int>(41));
    for(int i = 0; i <= commodity.size(); i++){
        vec[i][0] = 1;
    }
    for(int i = 1; i <= commodity.size(); i++){
        for(int j = 1; j <= 40; j++){
            if(j - commodity[i - 1] < 0){
                vec[i][j] = vec[i - 1][j];
            }
            else{
                vec[i][j] = vec[i - 1][j] + vec[i - 1][j - commodity[i - 1]];
            }
        }
    }
    //cout << vec[commodity.size()][40];

    //为了节约空间，采用一维数组
    vector<int> arr(41);
    for(int i = 1; i <= commodity.size(); i++){
        for(int j = 40; j >= 1; j--){
            arr[j] = arr[j] + (j - commodity[i - 1] > 0 ? arr[j - commodity[i - 1]] : (j - commodity[i - 1] == 0 ? 1 : 0));
            //也可以这么写
            // if(j - commodity[i - 1] > 0){
            //     arr[j] = arr[j] + arr[j - commodity[i - 1]];
            // }
            // if(j - commodity[i - 1] == 0){
            //     arr[j] = arr[j] + 1;
            // }
            // if(j - commodity[i - 1] < 0){
            //     arr[j] = arr[j];
            // }
        }
    }
    cout << arr[40];
}


int commoditySelect(vector<int> vec, int n, int v){
    if(v < 0) return 0;
    if(v == 0) return 1;
    if(n == 1) return vec[0] == v ? 1 : 0;
    return commoditySelect(vec, n - 1, v) + commoditySelect(vec, n - 1, v - vec[n - 1]);
}