网易校招题之牛牛的背包

题目描述

输入包括两行
第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。
第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积。

输出一个正整数, 表示牛牛一共有多少种零食放法。

3 10
1 2 4

8

三种零食总体积小于10,于是每种零食有放入和不放入两种情况，一共有2*2*2 = 8种情况。

#include<iostream>
using namespace std;
int methodCount = 1;

void DFS(long long v[], int size, long long w,long long curSum, int pos)
{
    if (curSum <= w)
    {
        ++methodCount;
        for (int i = pos + 1; i < size; ++i)
            DFS(v, size, w, curSum+v[i], i);
    }
    else
        return;
}

int main()
{
    int n;
    long long w;
    long long v[30];
    long long sum = 0;
    cin >> n >> w;
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
        sum += v[i];
    }
    //深度优先遍历，访问每个节点的下面的节点是否也符合条件
    //符合条件继续向下，不符合，回到上一层
    if (sum <= w)
        methodCount = 1 << n;
    else//对每个零食体积进行深搜
    {
        sort(v, v + n);
        for (int i = 0; i < n; ++i)
            DFS(v, n, w,v[i],i);
    }
        cout << methodCount << endl;
    return 0;
}