#1445. 特殊背包问题
特殊背包问题
题目描述
有N件物品和一个体积是的背包。
需要把一些物品装到背包里使得剩下的物品无法再放入,求方案数。
每件物品有一个体积。
输入格式
本题包含多组测试数据。
第一行输入一个整数,表示数据组数。
接下来对于每组数据的第一行是两个整数,,。
然后个整数,表示每个物品的体积。
输出格式
对于每个测试数据,输出个整数,第一个表示数据编号,第二个是题目要求的方案数。
样例
输入样例
2
6 25
8 9 8 7 16 5
30 250
1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
输出样例
1 15
2 16509438
提示
数据组数小于等于。
数据组数小于等于。
。