题解 | 神奇的口袋

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

//有20件物品,可知即使用递归，时间复杂度为2^n，计算量在1000000左右，不会超时

int a[21];
int mem[21][41];//状态表示数组

//求拿商品方法总数，m种商品，容积capacity
int ways(int m, int capacity) //实际上就是状态计算
{
    if (capacity < 0) //当容积小于0，方法数自然为0
        return 0;
    if (capacity == 0)
    {
        mem[m][capacity] = 1;//当容积为0时，方法数自然为1
        return 1;
    }
    if (m == 0 && capacity != 0)
    {
        mem[m][capacity] = 0;//此时方法数亦为0
        return 0;
    }
    if (mem[m][capacity] != -1)
    {
        return mem[m][capacity];//mem[m][capacity]非初始值-1时，存储的正是对应的方法数
    }
    else 
    {
        //递推关系的由来：首先状态表示数组mem[m][capacity]的含义是--
        //在最多选m件物品的前提下，总体积为capacity的方法数
        //故可以推出下列递推式
        //接着来看上文各种特殊情况的判定
        //
        mem[m][capacity] = ways(m - 1, capacity) + ways(m - 1, capacity - a[m]);
        return mem[m][capacity];
    }

}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < 21; i++)
    {
        for (int j = 0; j < 41; j++)
        {
            mem[i][j] = -1;//刷新状态数组
        }
    }
    cout << ways(n, 40) << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")