一定要使用动态规划
問題文
超市生鲜区 N 黄瓜的书正在销售。在收银台付款时,请检查您在生鲜区购买的黄瓜的总重量。 W 如果您购买以下产品,您将收到制作人三上的亲笔签名。
健介君很喜欢三上同学做的黄瓜,所以他想要尽可能多的签名。健介君请列出获得三上先生签名的方法。 有
課題
N 件行李,每件行李的重量均为正整数。 附上 a_i (1 ≦ i ≦ N)。
权重之和为 W 求行李件数,满足以下条件。
制約
- 1 ≦ N ≦ 1000.
- 1 ≦ W ≦ 1000.
- 1 ≦ a_i ≦ 1000.
入力
N W a_1 a_2 … a_N
出力
问题的解决办法 在 1 行输出。
入力例 1
4 4 1 1 2 3
出力例 1
11
\{\},\ \{a_1\},\ \{a_2\},\ \{a_3\},\ \{a_4\},\ \{a_1,\ a_2\},\ \{a_1,\ a_3\},\ \{a_2,\ a_3\},\ \{a_1,\ a_4\},\ \{a_2,\ a_4\},\ \{a_1,\ a_2,\ a_3\} 是满足条件的包的集合。