题解 | #神奇的口袋#

此题应该选择递归法，且递归思路为：
n个物品选择体积和为40的情况数目=
前n-1个物品选择体积和为40的情况数目+前n-1个物品选择体积和为 ‘40-第n个物品体积’ 的情况数目
以此递推。 当最后递推到只剩一个物品时，若要求从这一个物品中选择体积和为0的情况，即不选择，则返回1（因为此处不选择也是一种合法方案）
若要从这一个物品中选择体积和为x时，如果该物品体积恰好为x，显然这是一种选择，返回1
但如果该物品体积不是x，表明无法满足要求，及不存在方案，返回0
代码如下：

#include<stdlib.h>
#define vsum 40
int typenum(int v[], int n, int s);//表示从数组v[n]中选择某些物品使得体积和为s，共有多少情况。
int main(){
    int n;
    scanf("%d",&n);
    int v[n];
    for(int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    printf("%d", typenum(v, n, vsum));
    return 0;
}

int typenum(int v[], int n, int s){//n为数组长度，s为体积和
    if(s == 0) return 1;//当体积和为0时，表明不需要选择，这本身也是一种选择
    if(n == 1){
        if(v[0] != s) return 0;
        else return 1;
    }
    return (typenum(v, n-1, s) + typenum(v, n-1, s-v[n-1]));
}