01背包大背包问题

题目描述:

N个项目，编号为1, 2，…，N。对于每个i（ 1 ≤ i ≤ N ），项i的权重为 \( w_i \)，值为 \( v_i \)。芋头已经决定从N 件物品中挑选一些，并放在背包中。背包的容量为W，这意味着所取物品的重量之和不能超过W。

求芋头带回家的物品价值的最大可能和。

输入格式:

N W
w₁ v₁
w₂ v₂
：
w_N v_N

输出格式:

一个整数，表示芋头带回家的物品的最大可能值之和。

数据范围:

输入中的所有值都是整数。
1 ≤ N ≤ 100
1 ≤ W ≤ 10⁹
1 ≤ w_i ≤ W
1 ≤ v_i ≤ 10³

样例输入:

样例1：
3 8
3 30
4 50
5 60

样例2：
1 1000000000
1000000000 10

样例3：
6 15
6 5
5 6
6 4
6 6
3 5
7 2

样例输出:

样例1：
90

样例2：
10

样例3：
17

时间限制: 1000ms
空间限制: 256MB

---