A6920. 背包选礼物
编程题
普及-
知识点
题目描述
你打算在有限的背包容量内挑选若干件礼物。每件礼物都有重量和价值。每件礼物最多只能选一次。请在不超过背包总容量的前提下，使选中的礼物总价值最大。
输入格式
第一行包含两个整数 $n, W$，分别表示礼物数量和背包容量。
接下来 $n$ 行，每行两个整数 $w_i, v_i$，表示第 $i$ 件礼物的重量和价值。
接下来 $n$ 行，每行两个整数 $w_i, v_i$，表示第 $i$ 件礼物的重量和价值。
输出格式
输出一个整数，为在总重量不超过 $W$ 的前提下能获得的最大总价值。
输入输出样例
输入 #1
3 7 3 30 4 50 5 60
输出 #1
80
说明/提示
- $1 \le n \le 100$
- $1 \le W \le 100000$
- $1 \le w_i \le W$
- $1 \le v_i \le 10^9$
对于样例：
有三件礼物，容量 $W=7$。
选 ${3,4}$ 的总重量 $3+4=7$，总价值 $30+50=80$；
选 ${5}$ 的总价值 $60$；
选 ${3}$ 的总价值 $30$；
选 ${4}$ 的总价值 $50$。
最优是选 ${3,4}$，得到 $80$。
- $1 \le W \le 100000$
- $1 \le w_i \le W$
- $1 \le v_i \le 10^9$
对于样例：
有三件礼物，容量 $W=7$。
选 ${3,4}$ 的总重量 $3+4=7$，总价值 $30+50=80$；
选 ${5}$ 的总价值 $60$；
选 ${3}$ 的总价值 $30$；
选 ${4}$ 的总价值 $50$。
最优是选 ${3,4}$，得到 $80$。