专栏文章

题解：P1782 旅行商的背包

mmxbx
P1782题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mine1l8n
此快照首次捕获于
2025/12/02 00:53
3 个月前
此快照最后确认于
2025/12/02 00:53
3 个月前
查看原文

一.题目分析

题意简化为有大小为 CC 的背包，有 nn 件“普通物品”与 mm 件“奇物”, 适当选择使价值最大。
其中第 ii 件普通物品的体积、价值、数量分别为 ViV_{i}、WiW_{i}、DiD_{i}，第 ii 件奇物的价值 WW 与分配的体积 VV 关系满足 W(i,V)⁡=ai×V2+bi×V+ci\operatorname{W(i,V)} = a_{i} \times V^2 + b_{i} \times V + c_{i}。

二.思路讲解

Part1 总体思路

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

Part2 普通物品

I.子任务分析

对于普通物品，问题简化为“有大小为 CC 的背包，有 nn 件普通物品，其中第 ii 件普通物品的体积、价值、数量分别为 ViV_{i}、WiW_{i}、DiD_{i}，适当选择使价值最大。”

II.算法讲解

这是典型的完全背包模板，数据规模较大，把每个物品拆成 did_{i} 个直接进行 0/1背包 ，时间复杂度为 O(C∑i=1ndi)O(C \sum_{i=1}^nd_{i}) ，是肯定会 TLE 的，需要优化，这里采用 单调队列优化 至 O(nC)O(nC) ，如果你没有接触过单调队列，可以去尝试单调队列模板（tips：二进制拆分方案可以看其他题解，接下来是借题发挥讲一下单调队列优化完全背包，请视情况阅读）。
首先我们考虑一个体积、价值、数量分别为 V、W、DV、W、D 的物品。
为了使用单调队列，相邻决策的可选决策集合（意思就是可以从哪些状态转移而来）必须有重合且对应的价值单调以便直接选择最优解，显然相邻的两个体积（相差为1）不会存在重合的决策（除非 V=1V = 1）。
但如果只考虑状态 fjf_{j} ，不难得出能转移到状态 fjf_{j} 的策略集合是
{j−k×V∣k∈[0,D]}\{j - k \times V \mid k \in [0, D] \}
  • 注意：此处及后文书写的集合或方程都没有考虑部分边界条件，仅作推导，具体实现须考虑边界。
  • tips:其中 kk 的含义是选择 kk 个物品。（虽然这里考虑了不选此物品（即 k=0k = 0 情况），但由于使用一维数组，在具体实现中不选此物品的时，直接继承原来的值即可，无需计算）。
将上述集合稍作变形得到：
{u+k×V∣k∈[p−D,p−1]，u+p×V=j，u=j mod V}\{u + k \times V \mid k \in [p - D, p - 1]，u + p \times V = j，u = j \bmod V \}
  • tips:其中 kk 的含义是选择 (p−k)(p-k) 个物品。
从中可以发现状态 fxf_{x} 与状态 fyf_{y} 存在转移的必要条件是 x≡y(modV)x \equiv y \pmod V 。于是我们对于每个物品把体积 j∈[0,C]j \in [0,C] 分为 VV 类，所有关于 VV 同余的体积 jj 分为一类，易知不同类之间不会相互转移。
进而得到状态转移方程，对于每一个余数 uu ：
fu+p×V=max⁡p−D≤k≤p(fu+k×V+(p−k)∗W)f_{u + p \times V} = \max_{ p-D \le k \le p}(f_{u + k \times V} + (p-k) * W)
为了保证物品最多选 DD 个，必须只从上一阶段转移到当前阶段一次便于控制条件，观察到 u+k×V≤u+p×Vu + k \times V \le u + p \times V （由 kk 的定义可知），故我们倒序循环 pp 以保证 fu+k×Vf_{u + k \times V} 在当前阶段没被转移过，同时为了使 u+p×Vu + p \times V 完全覆盖 [0,C][0,C] 中的所有整数又不至于过大，我们让 pp 从 ⌊C−uV⌋\lfloor \dfrac{C - u}{V} \rfloor 开始倒序循环。
接下来讨论如何设计单调队列 qq 。观察 (fu+k×V+(p−k)∗W)(f_{u + k \times V} + (p-k) * W) ，不难发现在 i、ui、u 固定时，每次 p←p−1p \gets p-1 后原式中只有 p∗Wp * W 在变化，而 (fu+k×V−k∗W)(f_{u + k \times V} - k * W) 是定值且只由 kk 决定，故我们在队列中存放 kk 的值即可。
每次 p←p−1p \gets p-1 后， kk 的取值范围 [p−D,p−1][p - D, p- 1] 上下界都减小，新增决策 k=p−Dk = p -D ，而决策 k=pk = p 不再合法，所以对于每个 pp 我们做如下操作:
  • tips:接下来使用 qlq_{l} 与 qrq_{r} 分别表示队头与队尾， calc(k)⁡\operatorname{calc(k)} 表示 (fu+k×V−k∗W)(f_{u + k \times V} - k * W)
在每次转移后，我们需要加入新增决策 (p−D−1)(p-D-1) ，将其与队尾 qrq_{r} 比较，若 calc(qr)≤calc(p-D-1)⁡⁡\operatorname{calc(q_{r}) \le \operatorname{calc(p - D - 1)}} 就可以使队尾出队了（使 r←r−1r \gets r-1），因为队尾比当前决策先入队，按队列先进先出的规律，qrq_{r} 的“生命”短于当前决策，贡献又不比当前决策大，也就没有存在的价值了，剔除所有这样的“无价值决策”后使当前决策从队尾入队即可。所以我们的队列一定是 kk 单调递减且 calc(k)⁡\operatorname{calc(k)} 单调递减的。
在下一次转移前，我们需要保证队头的 kk 是合法的即 k∈[p−D,j]k \in [p - D, j] ，由于队头的 kk 是最大的，一直判断是否有 ql>p−1q_{l} > p-1 ，若有则从队头一直出队（使 l←l+1l \gets l+1）直至 ql≤p−1q_{l} \le p-1 。
接下来直接使用 qlq_{l} 作为最优决策转移即可（因为calc(ql)⁡\operatorname{calc(q_{l})} 是所有决策中最大的）。
  • 注意：在倒序循环 pp 前需要初始化队列。
把上述操作扩展到所有普通物品和每个余数即可。 程序留作课后习题，读者完成不难。

Part3 奇物

I.子任务分析

对于奇物，问题简化为“有大小为 CC 的背包，有 mm 件奇物，其中第 ii 件奇物的价值 WW 与分配的体积 VV 关系满足 W(i,V)⁡=ai×V2+bi×V+ci\operatorname{W(i,V)} = a_{i} \times V^2 + b_{i} \times V + c_{i}, 适当选择使价值最大。”

II.算法讲解

考虑到数据规模较小（m≤5m \le 5，C≤104C \le 10^4），可以直接对每种奇物枚举选择所有可能的体积取最大值，实现简单但有以下注意事项：
  1. 不能选同一种奇物选出多个体积单独计算价值后装入背包，必须由装入的总体积计算价值，所以要使用类似 0/1背包 的倒叙循环目标体积 jj。
  2. 而对于每个目标体积 jj 状态转移方程应为 fj=max⁡0≤V≤C(fj−V+W(i,V)⁡)f_{j} = \max_{0 \le V \le C}(f_{j - V} + \operatorname{W(i, V)})，注意从 V=0V = 0 开始枚举
  3. 特别的，W(i,0)⁡=max⁡(ci,0)\operatorname{W(i, 0)} = \max(c_{i}, 0)，表示若体积 V=0V = 0 时的收益为负可以选择不装。
此外，还有基于二次函数性质的小优化，根据二次函数的单调性，对于每个奇物以对称轴 V′=bi−2aiV' = \dfrac{b_{i}}{-2a_{i}} 为界，通过 aia_{i} 的正负分类讨论可以缩小需要枚举的体积边界，但优化程度微乎其微，最多也就减少 O(mC)O(mC) 次计算意义不大，此处就不进一步展开了 （懒得写了）。

Part4 后记

看到其他题解说单调队列优化过不了此题，我表示不服，遂作此题解 （其实主要是想借题发挥讲一讲单调队列优化）。
如果单调队列实在写不出来这里提供参考程序（未定义变量见上文含义）：
CPP
#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记录

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...