ZCMU1711 背包

Description

你有一个神奇的背包，他的容积是m(0<m<=80)，只有你装满他，你才能拿走他，现在给你n(1<=n<=20)个物品Xi(Xi<=m)，那么一共有几种方式，可以让你拿走背包？

Input

第一行 n,m

第二行 n个数字

Output

输出方案数

Sample Input

3 40

20 20 20

Sample Output

3

思路

题目名是背包，自然想到用背包问题解决，但是本题并没有涉及到价值和最优解，所以先留个坑给01背包，转而用更简单粗暴的DFS深度优先搜寻遍历所有情况，当满足情况计数器加一即可。

注意

数据不大，并不会超时。

代码

#include<bits/stdc++.h>
using namespace std;
int a[100];
int ans;
int m,n;
void dfs(int x,int y)
{
    if(x==0)
    {
        ans++;
        return;
    }
    if(x<0||y>n)
        return;
    dfs(x-a[y],y+1);
    dfs(x,y+1);
    return;
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        ans=0;
        dfs(m,1);
        cout<<ans<<endl;
    }
    return 0;
}