题解 | #神奇的口袋#

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

#include<stdio.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]));
}

#include<stdio.h>
#include<string.h>
int dp(int x,int n){
	int a[n];
    if(x==0)
        return 0;
    if(a[n]<x)
    	return dp(x,n-1)+dp(x-a[n],n-1);   
}
int main(){
    int i,n;
    int a[n];
    int x;
    scanf("%d",&x);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d\n",&a[i]);
    printf("%d\n",dp(x,n));
	return 0;
}  

此题应该选择递归法，且递归思路为：

n个物品选择体积和为40的情况数目=

前n-1个物品选择体积和为40的情况数目+前n-1个物品选择体积和为 ‘40-第n个物品体积’ 的情况数目

以此递推。 当最后递推到只剩一个物品时，若要求从这一个物品中选择体积和为0的情况，即不选择，则返回1（因为此处不选择也是一种合法方案）

若要从这一个物品中选择体积和为x时，如果该物品体积恰好为x，显然这是一种选择，返回1

但如果该物品体积不是x，表明无法满足要求，及不存在方案，返回0