1052. 0-1背包问题

单点时限: 2.0 sec

内存限制: 256 MB

已知 个物体 与一个背包。物体 的重量为 ,价值为 ,背包容量为

求在不超过背包容量的情况下,使得装进去的物体的价值最高。

输入格式

第一行为一个正整数 ,表示有几组测试数据。

每组测试数据的第一行为两个整数

再下去的 行每行有两个整数

输出格式

对于每组测试数据,输出一行,只含一个整数,表示装进去物体的价值最高值。

样例

Input
1
5 10
2 6
2 3
6 5
5 4
4 6
Output
15

575 人解决,738 人已尝试。

837 份提交通过,共有 2562 份提交。

5.4 EMB 奖励。

创建: 12 年,10 月前.

修改: 1 年,5 月前.

最后提交: 3 小时前.

来源: N/A

题目标签
DP