#P18637. Knapsack Problem
Knapsack Problem
Knapsack Problem
给定 个整数 和 个整数 。
你需要选择非负整数 ,满足对每一个 ,都有
$$\sum_{i=1}^{2^k-1} \left(\left\lfloor\frac{i}{2^j}\right\rfloor\bmod2\right)x_i=a_j.$$在满足全部条件的选择中,最大化
也就是说,类型 由它的 位二进制表示指定:第 位为 时,每选一个该类型就消耗第 维容量 ;第 位为 时不消耗该维容量。每种类型都可以选择任意非负整数个,各维容量必须恰好用完。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例占三行:
- 第一行一个整数 ;
- 第二行 个整数 ;
- 第三行 个整数 。
输出格式
对每个测试用例输出一行一个整数,表示最大价值。
数据范围
- ;
- ;
- ;
- 。
原题没有额外的各测试用例容量总和限制。答案需要使用 64 位有符号整数。
样例输入 1
3
2
1 2 4
4 5
3
3226252 19270256 2430652 1187613 12496062 10286165 17494834
24 85 34
4
901133 6693218 13245489 14740234 16186210 11382783 19277321 3855635 16523184 10168517 16195031 971041 10303441 8395899 11618555
529321239 218214127 92942310 207467810
样例输出 1
18
1949753378
7832404777567179
样例中的每种价格序列在实际输入中占一整行;这里保留完整数据,没有省略或用于排版的反斜杠。