神奇的口袋(百练2755) 描述 有一个神奇的口袋,总的容积是40,用这个口袋可以变出一些物品,这些物品的总体积必须是40。John现在有n个想要得到的物品,每个物品的体积分别是a1,a2……an。John可以从这些物品中选择一些,如果选出的物体的总体积是40,那么利用这个神奇的口袋,John就可以得到这些物品。现在的问题是,John有多少种不同的选择物品的方式。 输入 输入的第一行是正整数n (1 <= n <= 20),表示不同的物品的数目。接下来的n行,每行有一个1到40之间的正整数,分别给出a1,a2……an的值。 输出 输出不同的选择物品的方式的数目。 样例输入 3 20 20 20 样例输出 3 枚举,最大2^20. 递归求解 C/C++ (clang++ 3.3) 1#include<stdio.h>2#include<string.h>3#include<algorithm>4#include<iostream>5using namespace std;6int a[50];7int way(int w, int k)8{9 if(w==0) return 1;10 if(k==0) return 0;11 else12 return way(w, k-1)+way(w-a[k], k-1); //无限的循环,什么时候才是结尾(蛇吞尾)13}14int main()15{16 memset(a, 0, sizeof(a));17 int n;18 cin>>n;19 for(int i=1; i<=n; i++)20 cin>>a[i];21 cout<<way(40, n)<<endl;22 return 0;23}C/C++ (clang++ 3.3) 1 //动规方法求解 #include<iostream> 2 using namespace std; 3 int a[50]; 4 int way[50][50]; //way[w][k]表示 k个元素组成w的方法数 5 int main() 6 { 7 int n; 8 cin>>n; 9 for(int i=1; i<=n; i++) 10 { 11 cin>>a[i]; 12 way[0][i]=1; 13 } 14 way[0][0]=1; 15 for(int w=1; w<=40; w++) 16 for(int k=1; k<=n; k++) 17 { 18 way[w][k]=way[w][k-1]; //? 19 if(w-a[k]>=0) 20 { 21 way[w][k]+=way[w-a[k]][k-1]; //miracle 22 } 23 } 24 cout<<way[40][n]; 25 26 return 0; 27 } 永远渴望,大智若愚(stay hungry, stay foolish)