Responsive image

问题 1176 --又见01背包

1176: 又见01背包

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 3
[提交][状态][讨论版][命题人:]

题目描述

相信大家都对01背包了如指掌了。为了让大家巩固一下，ACMer决定再出一道题来考考大家。现在有n个重量和价值分别为wi 和 vi 的物品，背包的容量为W。要求从这些物品中选择总重量不超过 W 的物品，所挑选的方案是物品价值总和的最大。
1 <= n <=100
1 <= wi <= 10^7
1 <= vi <= 100
1 <= W <= 10^9

输入描述

有多组测试数据
每组测试数据第一行输入，n 和 W 。
接下来有n行，每行输入两个数，代表第i个物品的wi 和 vi。

输出描述

满足题意的最大价值，每组测试数据占一行。

样例输入

4 5
2 3
1 2
3 4
2 2
6 8
10 1
8 5
3 7
2 6
5 3
4 2

样例输出

7
13

来源

黄庆浩 

[提交][状态]
ACM算法攻关部