AT_dp_d Knapsack 1

有 $N$ 个物品。每个物品编号为 $1, 2, \ldots, N$。对于每个 $i$（$1 \leq i \leq N$），物品 $i$ 的重量为 $w_i$，价值为 $v_i$。 太郎君打算从这 $N$ 个物品中选择一些，放入背包带回家。背包的容量为 $W$，所选物品的总重量不能超过 $W$。 请你求出太郎君能带回家的物品的最大总价值。

输入通过标准输入按以下格式给出。 > $N$ $W$ $w_1$ $v_1$ $w_2$ $v_2$ $\ldots$ $w_N$ $v_N$

输出太郎君能带回家的物品的最大总价值。

## 限制条件 - 所有输入均为整数。 - $1 \leq N \leq 100$ - $1 \leq W \leq 10^5$ - $1 \leq w_i \leq W$ - $1 \leq v_i \leq 10^9$ ## 样例解释 1 选择物品 $1$ 和 $3$ 即可。此时总重量为 $3 + 5 = 8$，总价值为 $30 + 60 = 90$。 ## 样例解释 2 答案可能超过 32 位整数的范围。 ## 样例解释 3 选择物品 $2, 4, 5$ 即可。此时总重量为 $5 + 6 + 3 = 14$，总价值为 $6 + 6 + 5 = 17$。 由 ChatGPT 4.1 翻译