AT_abc032_d [ABC032D] ナップサック問題

请解决 0/1 背包问题。0/1 背包问题的定义如下： - 有 $N$ 个物品，第 $i\ (1\leq i\leq N)$ 个物品有价值 $v_i$ 和重量 $w_i$。 - 有一个最大承重为 $W$ 的背包。 - 请选择若干个物品放入背包，使得总重量不超过 $W$，并且总价值最大。每个物品最多只能选择一次。

输入以如下格式从标准输入读入。 > $N$ $W$ > $v_1$ $w_1$ > $v_2$ $w_2$ > $\vdots$ > $v_N$ $w_N$ - 第 $1$ 行包含两个整数，分别表示物品数量 $N\ (1\leq N\leq 200)$ 和背包的最大承重 $W\ (1\leq W\leq 10^9)$，以空格分隔。 - 接下来的 $N$ 行，每行包含两个整数，第 $i$ 行表示第 $i$ 个物品的价值 $v_i\ (1\leq v_i\leq 10^9)$ 和重量 $w_i\ (1\leq w_i\leq 10^9)$，以空格分隔。 - 下列三个条件中至少有一个成立：「$N\leq 30$」、「所有 $i\ (1\leq i\leq N)$ 满足 $1\leq w_i\leq 1000$」、「所有 $i\ (1\leq i\leq N)$ 满足 $1\leq v_i\leq 1000$」。

请输出一个整数，表示能够达到的最大总价值。输出后需换行。

## 部分分 本题设有部分分，满分为 $100$ 分。 - 若正确解决满足 $N\leq 30$ 的数据集 1，可获得 $34$ 分。 - 若正确解决满足 $N\leq 200$ 且所有 $i\ (1\leq i\leq N)$ 满足 $1\leq w_i\leq 1000$ 的数据集 2，可额外获得 $33$ 分。 - 若正确解决满足 $N\leq 200$ 且所有 $i\ (1\leq i\leq N)$ 满足 $1\leq v_i\leq 1000$ 的数据集 3，可额外获得 $33$ 分。 ## 样例解释 1 选择第 $2$ 个和第 $3$ 个物品，总重量为 $10$，总价值为 $16$，可以达到最大价值。该输入输出样例满足数据集 $1,2,3$ 的约束，因此用于所有数据集的评测。 ## 样例解释 2 该输入输出样例仅满足数据集 $1$ 的约束，因此不用于数据集 $2,3$ 的评测。 ## 样例解释 3 该输入输出样例不满足数据集 $3$ 的约束，因此不用于数据集 $3$ 的评测。 ## 样例解释 4 该输入输出样例不满足数据集 $2$ 的约束，因此不用于数据集 $2$ 的评测。 由 ChatGPT 4.1 翻译