P091 0/1 背包问题

题目描述

有 n 个物品，第 i 个物品重量 wi、价值 vi。背包容量为 W，每个物品最多选一次，求能获得的最大价值。

输入格式

第一行 n, W（1 \le n \le 500，1 \le W \le 10^5）。
接下来 n 行，每行 wi, vi（1 \le wi \le W，1 \le vi \le 10^4）。

输出格式

最大价值。

样例

输入:
4 5
2 3
1 2
3 4
4 5

输出: 7