有一个神奇的口袋，总的容积是40，用这个口袋可以变出一 些物品，这些物品的总体积必须是40。

John现在有n（1≤n ≤ 20）个想要得到的物品，每个物品 的体积分别是a1，a2……an。John可以从这些物品中选择一 些，

如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。 

 输入：

输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的 数目。

接下来的n行，每行有一个1到40之间的正整数，分别 给出a1，a2……an的值。

输出：

输出不同的选择物品的方式的数目。

输入样例：

3

20 20 20

输出样例：

3

分析：可以用两种方法解决-递归和动态规划

递归解法：

#include
     
       #include
      
       using namespace std;#define N 20 + 5int n;int a[N];int ans;int jz[N];void dfs(int cur, int v) {    if(cur > n || v > jz[cur] || v < a[cur]) return;//剪枝     if(v == a[cur]) {        ans++;        dfs(cur+1, v);    } else {        dfs(cur+1, v);        dfs(cur+1, v-a[cur]);            }    }int main() {    while(cin >> n) {        for(int i = 1; i <= n; i++) cin >> a[i];         sort(a+1, a+n+1);        jz[n] = a[n];        for(int i = n-1; i >= 1; i--) jz[i] = jz[i+1] + a[i];          ans = 0;        dfs(1, 40);        printf("%d\n", ans);    }    return 0;}
      
     

动态规划：

状态：把dp[i][j]定义为前j个物品拼成体积为i的方法数

状态转移方程：dp[i][j] += dp[i - a[j]][j-1]; 

注意：dp[i][j]在最开始应该被赋值为dp[i][j-1]，因为前j个物品包含了这j-1个物品

代码：

#include
     
      using namespace std;#define N 20 + 5int dp[N][N]; int a[N];int main() {    int n;    while(cin >> n) {        memset(dp, 0, sizeof(dp));        for(int i = 1; i <= n; i++) cin >> a[i];         for(int i = 0; i <= n; i++) dp[0][i] = 1;        for(int i = 0; i <= 40; i++) {            for(int j = 1; j <= n; j++) {                dp[i][j] = dp[i][j-1];                if(i >= a[j])                      dp[i][j] += dp[i - a[j]][j-1];            }        }        cout << dp[40][n] << endl;    }    return 0;}