問題文
世界上有一种叫做背包问题的东西,其想法是在一定大小的背包中装满物品,使其尽可能有价值,但思考这个问题是没有意义的。
无论价值有多高,我都不能浪费背包里的空间。我讨厌无用的东西。
现在,这是尺寸。 X 背包和 有 N 项。 第
i 项的大小为 w_i 。忽略该物品的价值,因为考虑它是毫无意义的。
有多少种方法可以将物品装入背包而不浪费空间?
换句话说,N 从单品来看,总尺寸堪称完美,没有浪费。 X 有多少种选择?
我尝试直接解决这个问题,但结果证明这是一种浪费的方法,所以我决定问你。
我希望你能帮助我编写一个程序来解决这个问题,而不浪费计算时间,从而节省我的时间。
入力
输入将以以下形式通过标准输入给出。
N X w_1 w_2 : w_N
- 1 行包含一个表示项目数的整数。 N (1 \leq N \leq 32) 和一个表示背包大小的整数 X (1 \leq X \leq 10^9) 由半角空格分隔。 来自行
- 2 在 N 行中,给出了项目的大小。其中 一个整数,表示第 i (1 \leq i \leq N) 行中,i 个项目的大小 写入 w_i (1 \leq w_i \leq 5 \times 10^7) 。
出力
入力例1
5 5 1 1 2 3 4
出力例1
4如何选择不浪费的物品如下。 4 没错。 选择
- 品物 1, 品物 2, 品物 4 : 1 + 1 + 3 = 5
- 品物 1, 品物 5 : 1 + 4 = 5
- 品物 2, 品物 5 : 1 + 4 = 5
- 品物 3, 品物 4 : 2 + 3 = 5
入力例2
8 21 10 4 2 30 22 20 8 14
出力例2
0无论您如何选择商品,它们的尺寸总和都是完美的。 不能将其设为 21 。
入力例3
20 100000000 35576749 38866484 6624951 39706038 11133516 25490903 14701702 17888322 14423251 32111678 24509097 43375049 35298298 21158709 30489274 37977301 19510726 28841291 10293962 12022699
出力例3
45
入力例4
16 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例4
12870