← 返回题单
题单练习 资源分配型DP入门
← 上一题 下一题 →

A6992 | Knapsack 2

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有 $N$ 个物品，编号为 $1, 2, \ldots, N$。对于每个 $i$ ($1 \leq i \leq N$)，物品 $i$ 的重量是 $w_i$，价值是 $v_i$。

太郎君决定从这 $N$ 个物品中挑选一些放入背包带回家。背包的容量为 $W$，这意味着所选物品的总重量不能超过 $W$。

请计算太郎君能带回的物品的最大总价值。

输入格式

第一行包含两个整数 $N$ 和 $W$，分别表示物品的数量和背包的容量。

接下来 $N$ 行，每行包含两个整数 $w_i$ 和 $v_i$，表示第 $i$ 个物品的重量和价值。

输出格式

输出一个整数，表示太郎君能带回的物品的最大总价值。

输入输出样例

输入 #1
3 8
3 30
4 50
5 60
输出 #1
90
输入 #2
1 1000000000
1000000000 10
输出 #2
10
输入 #3
6 15
6 5
5 6
6 4
6 6
3 5
7 2
输出 #3
17
C++ 编辑器
输入
输出