题解：P1782 旅行商的背包

· · 题解

Part1 总体思路

普通物品与奇物的选择除了共用体积外没有限制，所以可以分别结算，使用 f_{j} 表示“恰使用 j 的体积可以获得的最大价值”进行 DP 即可。

Part2 普通物品

这是典型的完全背包模板，数据规模较大，把每个物品拆成 d_{i} 个直接进行 0/1背包，时间复杂度为 O(C \sum_{i=1}^nd_{i})，是肯定会 TLE 的，需要优化，这里采用单调队列优化至 O(nC)，如果你没有接触过单调队列，可以去尝试单调队列模板（tips：二进制拆分方案可以看其他题解，接下来是借题发挥讲一下单调队列优化完全背包，请视情况阅读）。

首先我们考虑一个体积为 V 价值为 W 数量为 D 的物品。

为了使用单调队列，相邻转态的可选决策集合（意思就是可以从哪些状态转移而来）必须有重合且对应的价值单调以便直接选择最优解，显然相邻的两个体积（相差为1）不会存在重合的决策（除非 V = 1）。

但如果只考虑状态 f_{j}，不难得出能转移到状态 f_{j} 的策略集合是

\{j - k \times V \mid k \in [1,D] \}

将上述集合稍作变形得到：

\{u + k \times V \mid k \in [p - D,p - 1],u + p \times V = j,u = j \bmod V \}

从中可以发现状态 f_{x} 与状态 f_{y} 存在转移的必要条件是 x \equiv y \pmod V。于是我们对于每个物品把体积 j \in [0,C] 分为 V 类，所有关于 V 同余的体积 j 分为一类，易知不同类之间不会相互转移。

进而得到状态转移方程，对于每一个余数 u：

f_{u + p \times V} = \max_{ p-D \le k \le p - 1}(f_{u + k \times V} + (p-k) \times W)

为了保证物品最多选 D 个，必须只从上一阶段转移到当前阶段一次便于控制条件，观察到 u + k \times V \le u + p \times V（由 k 的定义可知），故我们倒序循环 p 以保证 f_{u + k \times V} 在当前阶段没被转移过，同时为了使 u + p \times V 完全覆盖 [0,C] 中的所有整数又不至于过大，我们让 p 从 \lfloor \dfrac{C - u}{V} \rfloor 开始倒序循环。

接下来讨论如何设计单调队列 q。观察 (f_{u + k \times V} + (p-k) \times W)，不难发现在 i 和 u 固定时，每次 p \gets p-1 后原式中只有 p \times W 在变化，而 (f_{u + k \times V} - k \times W) 是定值且只由 k 决定，故我们在队列中存放 k 的值即可。

每次 p \gets p-1 后，k 的取值范围 [p - D, p- 1] 上下界都减小，新增决策 k = p - D，而决策 k = p 不再合法，所以对于每个 p 我们做如下操作:

在每次转移后，我们需要加入新增决策 (p-D-1)，将其与队尾 q_{r} 比较，若 \operatorname{calc}(q_{r}) \le \operatorname{calc}(p - D - 1) 就可以使队尾出队了（使 r \gets r-1），因为队尾比当前决策先入队，按队列先进先出的规律，q_{r} 的“生命”短于当前决策，贡献又不比当前决策大，也就没有存在的价值了，剔除所有这样的“无价值决策”后使当前决策从队尾入队即可。所以我们的队列一定是 k 单调递减且 \operatorname{calc}(k) 单调递减的。

在下一次转移前，我们需要保证队头的 k 是合法的即 k \in [p - D, p - 1]，由于队头的 k 是最大的，一直判断是否有 q_{l} > p-1，若有则从队头一直出队（使 l \gets l+1）直至 q_{l} \le p-1。

接下来直接使用 q_{l} 作为最优决策转移即可（因为\operatorname{calc}(q_{l}) 是所有决策中最大的）。

把上述操作扩展到所有普通物品和每个余数即可。程序留作课后习题，读者完成不难。

Part3 奇物

考虑到数据规模较小（m \le 5，C \le 10^4），可以直接对每种奇物枚举选择所有可能的体积取最大值（接下来约定使用 \operatorname{W}(i, V) 表示第 i 个奇物表示分配体积 V 的价值），实现简单但有以下注意事项：

  1. 不能选同一种奇物选出多个体积单独计算价值后装入背包，必须由装入的总体积计算价值，所以要使用类似 0/1背包 的倒序循环目标体积 j。
  2. 而对于每个目标体积 j 状态转移方程应为 f_{j} = \max_{0 \le V \le C}(f_{j - V} + \operatorname{W}(i, V))，注意从 V = 0 开始枚举。
  3. 特别的，\operatorname{W}(i,0) = \max(c_{i}, 0)，表示若体积 V = 0 时的收益为负可以选择不装。

此外，还有基于二次函数性质的小优化，根据二次函数的单调性，对于每个奇物以对称轴 V' = \dfrac{b_{i}}{-2a_{i}} 为界，通过 a_{i} 的正负分类讨论可以缩小需要枚举的体积边界，但优化程度微乎其微，最多也就减少 O(mC^2) 次计算意义不大，此处就不进一步展开了 （懒得写了）。

Part4 后记

看到其他题解说单调队列优化过不了此题，我表示不服，遂作此题解 （其实主要是想借题发挥讲一讲单调队列优化），更多是对单调队列优化完全背包的详解。但单调队列常数确实很大，考虑缓存未命中导致的效率下降，估算时间复杂度时建议将常数当 10（由于本题 d_{i} \le 10^3，二进制拆分后时间复杂度是 O(C \sum_{i=1}^n \log_2 d_{i}) 而 \log_2 d_{i} < 10，所以效率可能还真不如二进制拆分）。

如果单调队列实在写不出来这里提供参考程序（未定义变量见上文含义）：

#define calc(k) (f[u + (k) * a[i].v] - (k) * a[i].w)

int q[2005];
for (int i = 1; i <= n; ++i) {
      for (int u = 0; u < a[i].v; ++u) {
          int l = 1, r = 0;
          int maxp = (c - u) / a[i].v;
          for (int k = maxp-1; k >= maxp - a[i].d && k >= 0; --k) {
              while (l <= r && calc(q[r]) <= calc(k)) --r;
              q[++r] = k;
          }
          for (int p = maxp; p >= 0; --p) {
              while (l <= r && q[l] > p-1) ++l;
              if (l <= r) f[u + p*a[i].v] = max(f[u + p*a[i].v], calc(q[l]) + p*a[i].w);
              if (p - a[i].d - 1 >= 0) {
                  while (l <= r && calc(q[r]) <= calc(p-a[i].d-1)) --r;
                  q[++r] = p - a[i].d - 1;
              }
          }
      }
  }

最后，点击查看AC记录