分数: 366 分
问题陈述
高桥作为一名冒险家,潜入了古代遗迹的宝库。有 N 金库里的宝藏,高桥正试图将它们装进背包带回家。
每件宝物 i (1 \leq i \leq N) 的权重为 w_i 公斤和价值 v_i.
高桥的背包最多可容纳总重量为 W 公斤。对于每个 N 宝物,高桥选择是否放入背包。每件宝物最多有一个,并且不可能将一件宝物拆分出来,只将一部分放入背包中。
高桥想要最大化所选宝物的总价值,但受限于所选宝物的总重量最多为 W 公斤。
找到最大可能的总值。
约束
- 1 \leq N \leq 100
- 1 \leq W \leq 10^5
- 1 \leq w_i \leq W
- 1 \leq v_i \leq 10^9
- 所有输入均为整数。
输入
N W w_1 v_1 w_2 v_2 \vdots w_N v_N
- 第一行包含宝藏数量 N 和背包容量 W,用空格分隔。
- 的 i- 以下各项 N 行(1 \leq i \leq N) 包含重量 w_i 和值 v_i 宝藏 i,用空格分隔。
输出
在一行上打印所选宝藏的最大可能总价值。
示例输入 1
3 8 3 30 4 50 5 60
示例输出 1
90
示例输入 2
5 15 2 10 3 20 5 30 7 40 9 50
示例输出 2
90
示例输入 3
10 50 12 150 8 90 15 200 6 80 20 250 3 40 10 120 18 220 5 60 25 300
示例输出 3
640