1426-大卖场购物车1


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:3 提交数:5 难度:5


题目描述:

央视有一个大型娱乐节目购物街,舞台上模拟超市大卖场,有很多货物,每个嘉宾分配一个购物车,可以尽情地装满购物车,购物车中装的货物价值最高者取胜。假设有n个物品和1个购物车,每个物品i对应价值为vi,重量wi,购物车的容量为W(你也可以将重量设定为体积)。每个物品只有1件,要么装入,要么不装入,不可拆分。在购物车不超重的情况下,如何选取物品装入购物车,使所装入的物品的总价值最大? 


输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据第一行输入,n 和 W(1 <= n <=40,1 <= W <= 1000),接下来有n行,每行输入两个数,代表第i个物品的重量wi 和价值 vi(1 <= wi,vi <= 1000)。

输出描述:

对于每一组输入,输出满足题意的最大价值。
每组的输出占一行。

样例输入:

2
5 10
2 6
5 3
4 5
2 4
3 6
4 52
12 13
10 24
22 13
9 24

样例输出:

17
61

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!