题目描述
有一个神奇的口袋, 总的容积是 40, 用这个口袋可以变出一些物品, 这些物品的总体积必须是 40.John 现在有 n 个想要得到的物品, 每个物品的体积分别是 a1,a2......an.John 可以从这些物品中选择一些, 如果选出的物体的总体积是 40, 那么利用这个神奇的口袋, John 就可以得到这些物品. 现在的问题是, John 有多少种不同的选择物品的方式.
输入描述:
输入的第一行是正整数 n (1 <= n <= 20), 表示不同的物品的数目. 接下来的 n 行, 每行有一个 1 到 40 之间的正整数, 分别给出 a1,a2......an 的值.
输出描述:
输出不同的选择物品的方式的数目.
分析:
题目的意思就是在 n 个数里面找到和为 40 的组合个数, 和为 40 的组合种类.
递归方法
考虑数组里的一个数 a[i], 可以选择加入这个数 a[i], 也可以选择不加入
当选择要加入 a[i] 时, 组合种类就是
count(i + 1, sum - a[i])
- #include <iostream>
- using namespace std;
- int a[21];
- int n;
- int count(int i, int sum){
- if(sum == 0) return 1;// 当体积被耗尽也就是和足够 40, 说明找到了一种组合的方法
- else if(i == n || sum <0) return 0;// i == n 说明用尽了所有的数也找不到一种组合
- else return count(i + 1, sum - a[i]) + count(i + 1, sum); // 选择加入 a[i] 或者不加入 a[i]
- }
- int main(){
- //int n;
- while(cin>> n){
- for(int i = 0; i <n; i++){
- cin>> a[i];
- }
- cout << count(0, 40) << endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2930647.html