5820: 4.9 大卖场购物车1
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:89
解决:66
题目描述
央视有一个大型娱乐节目——购物街,舞台上模拟超市大卖场,有很多货物,每个嘉宾分配一个购物车,可以尽情地装满购物车,购物车中装的货物价值最高者取胜。假设有n个物品和1个购物车,每个物品 i 对应价值为 v,重量 w ,购物车的容量为W(你也可以将重量设定为体积)。每个物品只有1件,要么装入,要么不装入,不可拆分。在购物车不超重的情况下,如何选取物品装入购物车,使所装入的物品的总价值最大?
输入
样例的组数
t ( 0 < t < 10 )
物品个数
n ( 0 < n < 100 )
购物车的容量
W ( 0 < w < 1000 )
依次输入每个物品的重量 w 和价值 v ( 0 < wi,vi < 1000 )
w1 v1 w2 v2 ... wn vn
t ( 0 < t < 10 )
物品个数
n ( 0 < n < 100 )
购物车的容量
W ( 0 < w < 1000 )
依次输入每个物品的重量 w 和价值 v ( 0 < wi,vi < 1000 )
w1 v1 w2 v2 ... wn vn
输出
购物车装入的最大价值
ans
ans
样例输入 复制
1
5
10
2 6 5 3 4 5 2 4 3 6
样例输出 复制
17