P9140 [THUPC 2023 初赛] 背包

本题中，你需要解决完全背包问题。 有 $n$ 种物品，第 $i$ 种物品单个体积为 $v_i$、价值为 $c_i$。 $q$ 次询问，每次给出背包的容积 $V$，你需要选择若干个物品，每种物品可以选择任意多个（也可以不选），在选出物品的体积的和**恰好**为 $V$ 的前提下最大化选出物品的价值的和。你需要给出这个最大的价值和，或报告不存在体积和恰好为 $V$ 的方案。 为了体现你解决 NP-Hard 问题的能力，$V$ 会远大于 $v_i$，详见数据范围部分。

无

无

#### 样例解释 1 第二组询问的最优方案为：选择 $3$ 个物品 $1$ 和 $12499999998$ 个物品 $2$。 #### 子任务 对于所有测试数据，$1 \le n \le 50, 1 \le v_i \le 10^5, 1 \le c_i \le 10^6, 1 \le q \le 10^5, 10^{11} \le V \le 10^{12}$。 #### 题目来源 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。 题解等资源可在 查看。