← 返回题目列表

AtCoder · awc0110_c

C. 背包和宝藏

中文机器翻译题面 查看原题

分数: 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