poj 2755(递归)

   神奇的口袋

总时间限制:

10000ms

内存限制:

65536kB

 

描述

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

输入

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

输出

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

样例输入

3
20
20
20

样例输出

3

  解题思路：

1.设fun(a1,a2....an,40)为a1,a2....an凑出40的方法数。

考虑凑数的方法分为两类:

有a1 和没有a1,则可以得

fun(a1,...an,40)  = fun(a2.....an,40-a1)  //有a1

  + fun(a2......an,40) ;//没a1

我们把a1.....an所有整数放到一个数组a中,n表示数组中

整数的个数,i表示从第i个整数开始凑数,sum,表示要凑出

的整数，则可得公式

fun(a,n,i,sum) = fun(a,n,i+1,sum-a[i])//用到a[i]
 + f(a,n,i+1,sum) ;//不用a[i]

2.递归出口说明
如果sum等于0，说明前面已经找到一种成功的组合方式，返回1，否则，就是sum不等于0
如果i==n，说明没有可选的数来完成这一组和方式，返回0，如果sum<0，说明刚刚尝试的组合凑不出要组合的数，所以返回0 

3.解决方法： G++

#include<iostream>
using namespace std ;
int a[21] ;
int n ;
int fun(int i,int sum)
{
 if(sum==0)  return 1 ;
 if(i==n||sum<0) return 0 ;
 return fun(i+1,sum-a[i]) + fun(i+1,sum) ;
}
int main()
{
 int i,t;
 cin>>n ;
for(i=0;i<n;i++)
    cin>>a[i] ;
  t = fun(0,40);
cout<<t<<endl;
    return 0 ;
}