牛客 牛牛的背包问题

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

题目描述

牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。 牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。 牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。

输入描述:

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

输出描述:

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

示例1

输入

3 10
1 2 4

输出

8

说明

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

自顶向下，如果能装下，则方案数为装+不装的方案。

N,W = list(map(int,input().split()))
V = list(map(int, input().split()))
 
def count(W, V):
    if W<=0:return 1
    if len(V)<=0:return 1
    if sum(V)<=W:
        return 2**len(V)
    if V[0]<=W:
        return count(W-V[0], V[1:]) + count(W, V[1:])
    else:
        return count(W, V[1:])
print(count(W,V))