背包问题汇总1--牛牛的背包问题

链接：https://www.nowcoder.com/questionTerminal/bf877f837467488692be703735db84e6
来源：牛客网

牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为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,于是每种零食有放入和不放入两种情况，一共有222 = 8种情况。

提交通过的代码：
#include <stdio.h>
#include <string.h>
//不能采用0-1背包问题处理，数组太大了。
int fun(int n,int w,int* p)
{

if (w < 0)//本次递归时，发现背包容量已经不足
{
    return 0;
}
else if (0 == n)//递归完成
{
    if (w > * (p + n))//如果全部物品递归完成，还有余量，则本次最后放的物品可以加入背包
    {
        return 2;
    }
    else//如果加入最后一个物品，会超过背包容量，则不加入最后一个问题
    {
        return 1;
    }
}

return (fun(n - 1, w, p) + fun(n - 1, w - *(p + n),p));//递归，按照两个分支处理，加入最后一个物品，需要减掉背包容量；不加入最后一个物品，则不需要减掉背包的容量

}

int main(void)
{
int n = 0;
int* p;
long long sum = 0;
long long w = 0;
long long count = 0;

scanf("%d %d", &n, &w);

p = (int*)malloc(n * sizeof(int));

if (NULL == p)
{
    return 0;
}

for (int i = 0;i < n;i++)
{
    scanf("%d", (p + i));
    sum += *(p + i);
}

if (sum <= w)
{
    count = pow(2, n);//因为每件零食只有一件，所以如果全部零食的和都没有超过背包总容量，则按照每种零食可选可不选即可，即2的n次方
}
else//全部零食总容量超过背包容量，则需要递归，考虑第i件物品想放在包里，是否还有剩余空间
{
    count = fun(n - 1, w, p);
}

printf("%d", count);

return 0;

}