网易校招题之牛牛的背包
题目描述
牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。
牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。
牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。
输入描述:
输入包括两行 第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。 第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积。
输出描述:
输出一个正整数, 表示牛牛一共有多少种零食放法。
示例1
输入
3 10 1 2 4
输出
8
说明
三种零食总体积小于10,于是每种零食有放入和不放入两种情况，一共有2*2*2 = 8种情况。
如果n个零食的总体积小于背包体积，那么每种零食有放入和不放入两种情况，一共有2^n
如果n个零食的总体积大于背包体积，先排序，依次放入1号、2号。。。m号，直到体积大于背包体积，然后进行下一轮2号。。x号。。。
#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;
} 
查看15道真题和解析