2572. 01背包
1000ms
256MB
简单
动态规划
Dynamic Programming
题目描述
有 $n$ 个物品，编号为 $i$ 的物品的重量为 $w[i]$，价值为 $v[i]$。现在要从这些物品中选一些物品装到一个载重为 $m$ 的背包中，使得背包内物品的总重量不超过 $m$，并且总价值尽量大。
输入格式
第 1 行：两个整数 $n$ 和 $m$，分别表示物品数量和背包载重（$n \le 3500$，$m \le 12880$）。
第 $2$ 到第 $n+1$ 行：每行包含两个整数 $w[i]$ 和 $v[i]$，分别表示第 $i$ 个物品的重量和价值。
输出格式
仅一行，一个整数，表示能够获得的最大总价值。
样例 1
输入 (Input)
输出 (Output)
- $n \le 3500$
- $m \le 12880$
- $1 < w[i], v[i] \le 1000$
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功