Problem1241--01背包

1241: 01背包

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 280  Solved: 66
[Submit] [Status] [Web Board] [Creator:]

Description

现在PIPI有一个容量为w的背包,他想将n个物品放入背包内, 第i个物品体积为v[i]。
在不超过背包容量的情况下,PIPI想知道一共有多少种放法。
PS:任何东西都不装也是一种放法。

Input

输入包含多组测试样例。
第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2e9),表示物品的数量和背包的容量。
第二行n个正整数v[i](0 <= v[i] <= 2e9),表示每个物品的体积。

Output

对于每一组测试样例,输出方法数。

Sample Input

3 10
1 2 4

Sample Output

8

Source/Category

中等