P5454 [THUPC2018] 城市地铁规划 引发的思考--zhengjun

有如下背包问题：

• \(n\) 种物品，体积为 \(v_i\)，价值为 \(w_i\)，不限量，要求选 \(m\) 件物品，且总体积为 \(V\)，求总价值的最大（小）值。

解决方法：

• 不妨令 \(v_i\) 升序，首先先选 \(m\) 个 \(1\) 号物品，计算体积 \(V_0=m\times v_1\)，然后每选一件物品，就替换掉一件 \(1\) 号物品。

转移式：\(f_{i+v_j-v_1}\leftarrow f_i+w_j-w_1,j>1\)

初始：\(f_{m\times v_1}=m\times w_1\)

答案：\(f_V\)

复杂度：时间-\(O(nV)\)，空间-\(O(V)\)。

这样即可确保最终物品个数恰为 \(m\)，且体积为 \(V\)。

但是，这样做有条件，就是说不能达到所有的 \(v_1\) 都被替换了之后，体积没到 \(V\)，造成继续替换的后果。

所以，前提条件：\(v_2\times m \ge V\)，即要么都选 \(v_2\)，要么必有 \(v_1\)。