A6920 | 背包选礼物
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
你打算在有限的背包容量内挑选若干件礼物。每件礼物都有重量和价值。每件礼物最多只能选一次。请在不超过背包总容量的前提下，使选中的礼物总价值最大。
输入格式
第一行包含两个整数 $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$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？