题解：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] \}

注意：此处及后文书写的集合或方程都没有考虑部分边界条件，仅作推导，具体实现须考虑边界。
tips:其中 $k$ 的含义是选择 $k$ 个物品。（不选此物品时（即 $k = 0$ 情况），由于使用一维数组，直接继承原来的值即可，无需计算）。

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

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

tips:其中 $k$ 的含义是选择 $(p-k)$ 个物品。

从中可以发现状态

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

我们做如下操作:

tips:接下来使用 $q_{l}$ 与 $q_{r}$ 分别表示队头与队尾， $\operatorname{calc}(k)$ 表示 $(f_{u + k \times V} - k \times W)$ 。

在每次转移后，我们需要加入新增决策

(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})

是所有决策中最大的）。

注意：在倒序循环 $p$ 前需要初始化队列。

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

Part3 奇物

考虑到数据规模较小（

m \le 5

，

C \le 10^4

），可以直接对每种奇物枚举选择所有可能的体积取最大值（接下来约定使用

\operatorname{W}(i, V)

表示第

i

个奇物表示分配体积

V

的价值），实现简单但有以下注意事项：

不能选同一种奇物选出多个体积单独计算价值后装入背包，必须由装入的总体积计算价值，所以要使用类似 0/1背包 的倒序循环目标体积 $j$ 。
而对于每个目标体积 $j$ 状态转移方程应为 $f_{j} = \max_{0 \le V \le C}(f_{j - V} + \operatorname{W}(i, V))$ ，注意从 $V = 0$ 开始枚举。
特别的， $\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

，所以效率可能还真不如二进制拆分）。

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

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记录

题解：P1782 旅行商的背包

文章操作

Part1 总体思路

Part2 普通物品

Part3 奇物

Part4 后记

相关推荐

评论

题解：P1782 旅行商的背包