题目描述
有一个神奇的口袋, 总的容积是 40, 用这个口袋可以变出一些物品, 这些物品的总体积必须是 40.John 现在有 n 个想要得到的物品, 每个物品的体积分别是 a1,a2......an.John 可以从这些物品中选择一些, 如果选出的物体的总体积是 40, 那么利用这个神奇的口袋, John 就可以得到这些物品. 现在的问题是, John 有多少种不同的选择物品的方式.
输入
输入的第一行是正整数 n (1 <= n <= 20), 表示不同的物品的数目. 接下来的 n 行, 每行有一个 1 到 40 之间的正整数, 分别给出 a1,a2......an 的值.
输出
输出不同的选择物品的方式的数目.
样例输入
- 2
- 12
- 28
- 3
- 21
- 10
- 5
样例输出
1
0
思路
DP 问题, 等式 DP[w][i] = DP[w][i-1] + DP[w-a[i]][i-1]
每次分为取第 i 个与不取第 i 个两种, 取第 i 个则减去体积 a[i] .
代码
- #include <cstdio>
- using namespace std;
- int a[21];
- int foo(int w, int n)
- {
- if (w == 0)
- return 1;
- if (w < 0)
- return 0;
- if (n <= 0)
- return 0;
- return foo(w, n - 1) + foo(w - a[n], n - 1);
- }
- int main()
- {
- int n;
- while (scanf("%d", &n) && n != 0) {
- for (int i = 1; i <= n; i++)
- scanf("%d", &a[i]);
- printf("%d\n", foo(40, n));
- }
- return 0;
- }
[codeup] 2044 神奇的口袋
来源: http://www.bubuko.com/infodetail-2947532.html