简答题 偏难
#7253

神奇的口袋 有一个神奇的口袋,总的容积是40,用这个口袋可以变出一些物品,这些物品的总体积必须是40。John现在有n个想要得到的物品,每个物品的体积分别是a…

神奇的口袋

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

时间限制:10000

内存限制:65536

输入

输入的第一行是正整数n (1 <= n <= 20),表示不同的物品的数目。接下来的n行,每行有一个1到40之间的正整数,分别给出a1,a2……an的值。

输出

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

样例输入

3
20
20
20

样例输出

3
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int goods[30]; // 从前k种物品中选择一些,凑成体积w的做法数目 int ways(int w, int k) {   if (w == 0)     return 1; // 没有需要凑的体积了,刚好凑满   if (k &lt;= 0)     return 0; // 还差体积或者体积过了,但是没有物品可以选了。   if (w &gt;= goods[k]) {     return ways(w, k - 1) +            ways(w - goods[k], k - 1); // 体积:选择第k种物品 + 不选第k种物品   } else {     return ways(w, k - 1);   } } int main() {   int n;   scanf("%d", &amp;n);   for (int i = 1; i &lt;= n; i++) {     scanf("%d", &amp;goods[i]);   }   printf("%d", ways(40, n));   return 0; }</pre>
这道题暂未补解析。