神奇的口袋

 第一种是递归解法：

#include 
using namespace std;
int a[30], N;
int way(int w, int k) {
    //从k中物品中选择一些，凑成体积w的做法数目
    if (w == 0) return 1;
    if (k <= 0) return 0;
    return way(w, k - 1) + way(w - a[k], k - 1);
    //其实就是不选第k个（也就是最后一个物品）的选法加上选第k个的选法
}
int main() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
    }
    cout << way(40, N) << endl;
    return 0;
}

第二种是递推解法：

这个递推解法其实就是由递归推出来的

 从递归式子里就可以退出这个二维数组，所以如果要退出×这个位置有两种，第一种就是不取第k种（在二维数组的表现就是w-a[k]这个值突上去了），取k种就是w-a[k]的值没有突上去。这个地方在遍历二维数组的时候加上一个判断就好了

#include 
using namespace std;
int a[30], N;
int way[40][40];//这个way其实就是表示从前j种物品凑出体积i的方法数
int main() {
    cin >> N;
    memset(way, 0, sizeof(way));
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        way[0][i] = 1;
    }
    way[0][0] = 1;
    for (int w = 1; w <= 40; w++) {
        for (int k = 1; k <= N; k++) {
            way[w][k] = way[w][k - 1];
            if (w - a[k] >= 0) {
                way[w][k] += way[w - a[k]][k - 1];
            }
        }
    }
    cout << way[40][N];
}