AT_kupc2019_b ナップサック問題

有 $n$ 个物品，编号从 $1$ 到 $n$。 每个物品都有一个价值和一个重量，第 $i$ 个物品的价值为 $v_i$，重量为 $w_i$。 你可以从这些物品中选择若干个，使得所选物品的总重量不超过 $W$，并且使所选物品的总价值最大。 但是，有 $m$ 个条件。 第 $j$ 个条件为 $(a_j, b_j)$，表示“如果选择了第 $a_j$ 个物品，则必须选择第 $b_j$ 个物品；如果选择了第 $b_j$ 个物品，则必须选择第 $a_j$ 个物品”。 请在满足所有这些条件的前提下，从 $n$ 个物品中选择若干个，使得总重量不超过 $W$，并输出所能获得的最大总价值。

输入通过标准输入按以下格式给出。 > $n$ $m$ $W$ > $w_1$ $v_1$ > $w_2$ $v_2$ > $\vdots$ > $w_n$ $v_n$ > $a_1$ $b_1$ > $a_2$ $b_2$ > $\vdots$ > $a_m$ $b_m$

请输出在满足 $m$ 个条件的前提下，从 $n$ 个物品中选择若干个、且总重量不超过 $W$ 时所能获得的最大总价值。

### 限制条件 - 输入中的所有数值均为整数。 - $1 \leq n \leq 100$ - $0 \leq m \leq \frac{n(n-1)}{2}$ - $1 \leq W \leq 10^4$ - $1 \leq w_i \leq W$ - $1 \leq v_i \leq 10^7$ - $1 \leq a_i, b_i \leq n$ - $a_i \neq b_i$ - 若 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$ 且 $(a_i, b_i) \neq (b_j, a_j)$ ### 样例解释 1 可以选择第 $1$ 个和第 $2$ 个物品，使得总价值为 $6$，这是最优解。请注意，由于条件限制，不能只选择第 $2$ 个和第 $3$ 个物品。 ### 样例解释 2 可以选择所有物品。 ### 样例解释 3 无法选择任何物品。 由 ChatGPT 4.1 翻译