X-1 智取整数(复杂版)

Question

X-1 智取整数

题目将给出一个长度为n的整数数组A,A的第i个元素表示为ai,从数组A中任取k个下标不同的元素组成数组B,题目要求写出数组B中的所有元素之和不大于Q的最大值.

输入格式

第一行给出一个正整数T表示测试数据个数.
对于每组数据:
第一行给出2个整数n和Q,n代表数组A的长度,Q代表从A数组取出元素的总和不能超过的值.
第二行给出n个非零整数,第i个整数代表数组A中的第i个元素a[i].

输出格式

对于每组数据输出一个整数代表正确答案.
每组数据占一行,第i行代表第i组数据的答案.
题目保证给出的所有数据都有解.

数据范围

0<T<=10
0<n<=1000
0<|ai|<=5000
0<k<=n
|Q|<=10000
题目保证t组数据n的总和不超过1000

时间限制

time<=2000ms

输入样例1

3
4 10
2 4 7 7
5 15
5 8 11 -3 -4
5 17
5 8 11 -3 -4

输出样例1

9
15
17

样例1解释

第一个数据B数组为{2,7},B数组所有元素之和为9不超过10且最大,所以输出10;
第二个数据B数组为{8,11,-4},B数组所以元素之和为15不超过15且最大,所以输出15;
第三组数据B数组为{5,8,11,-3,-4},B数组所有元素之和为17不超过17且最大,所以输出17;

Answer 1

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7430222