算法题

题目描述有一个神奇的口袋总的容积是40用这个口袋可以变出一些物品这些物品的总体积必须是40。John现在有n个想要得到的物品每个物品的体积分别是a1a2……an。John可以从这些物品中选择一些如果选出的物体的总体积是40那么利用这个神奇的口袋John就可以得到这些物品。现在的问题是John有多少种不同的选择物品的方式。输入描述:输入的第一行是正整数n (1 n 20)表示不同的物品的数目。接下来的n行每行有一个1到40之间的正整数分别给出a1a2……an的值。输出描述:输出不同的选择物品的方式的数目。示例13 20 20 20输出3#include stdio.h using namespace std; int goods[21]; int num; void dfs(int n, int sum, int max) { if (n max) return; if (sum 40) return; if (goods[n] sum 40) num; dfs(n 1, sum, max); dfs(n 1, sum goods[n], max); } int main() { int n; while (scanf(%d, n) ! EOF) { num 0; for (int i 0; i n; i) scanf(%d, goods[i 1]); dfs(1, 0, n); printf(%d\n, num); } return 0; }没有使用背包简洁易懂但较慢某case set下10ms使用背包算法之后#include stdio.h using namespace std; int goods[21]; int map[41]; int main() { int n; while (scanf(%d, n) ! EOF) { for (int i 0; i n; i) { scanf(%d, goods[i 1]); } for (int i 0; i 41; i) { map[i] 0; } map[0] 1; for (int i 1; i n; i) { for (int j 40; j goods[i]; j--) { map[j] map[j] map[j - goods[i]]; } } printf(%d\n, map[40]); } return 0; }同等case set下4ms。