多重背包的贪心近似

题目大意

多重背包问题：

物品数 \(n\)
背包容量 \(m\)
第 \(i\) 种物品有 \(c_i\) 个，每个物品体积 \(t_i\)，价值 \(w_i\)

\(n,t_i\le 100,m,c_i,w_i\le 10^9\)

约定记号

问题的解 \(s\) 为长 \(n\) 的数列，物品 \(i\) 取 \(s_i\) 个
设性价比 \(r_i=w_i/t_i\)
设 \(t_{max}=\max_i t_i\)
设 \(T(s)=\sum_{i=1}^n s_it_i\)，即解的总时间
设 \(W(s)=\sum_{i=1}^n s_iw_i\)，即解的总价值
设最优解集合为 \(O=\{s|s~\text{is an optimal solution}\}\)

Solution

首先特判所有物品均可取完的情况。

之后我们可以假设：任何解都不会取完所有物品。这个性质将在后面的证明中使用。

观察数据范围：

\(n,t_i\) 非常小
\(m,c_i,w_i\) 很大

直觉上，按照性价比贪心，得到的解应该不会离某个最优解太远。因此我们前半段贪心，后半段用 DP 修正。

设按性价比从高到低贪心得到的解为 \(g\)。

有以下核心性质：

\[\boxed{ \exists x\in O, \forall i,\ |g_i-x_i|\le t_{\max} } \]

证明放在后面。

有了这个结论之后，对于每一种物品 \(i\)，我们可以限制最优解 \(x_i\) 的范围：

\[x_i\in \left[ \max(0,g_i-t_{\max}), \min(g_i+t_{\max},c_i) \right]. \]

因此每一种物品剩余的可变数量只有 \(O(t_{\max})\) 个。

由于 \(t_{\max}\le 100\)，只需要在这个小范围内做多重背包 DP 即可。

Proof

不妨重新编号，使得 \(r_1\ge r_2\ge\cdots\ge r_n\)。按照这个顺序贪心。

由贪心过程可知，存在唯一的 \(k\)，使得

\[\begin{aligned} &\forall ik, g_i=0 \\ \end{aligned} \]

引理

\(\forall x\in O\)，由于任何解都不会取完所有物品，有

\[\begin{aligned} m-T(g)&

因此

\[-t_{max}

记

\[H(s)=\sum_{i=1}^n|g_i-s_i|. \]

下面固定一个

\[x=\arg\min_{s\in O}H(s). \]

我们将证明 \(x\) 满足 \(\forall i,|g_i-x_i|\le t_{max}\)。

反设存在 \(a\)，使得 \(|g_a-x_a|>t_{\max}\)。分类讨论拆绝对值。

情况一：\(\exists a,g_a-x_a>t_{max}\)

定义

\[\begin{aligned} & \Delta_{-} = \sum_{x_ig_i}t_i(x_i-g_i) \le \sum_{x_i>g_i}t_{max}(x_i-g_i) \end{aligned} \]

有

\[T(x)-T(g)=\Delta_{-}+\Delta_{+} \]

由引理得

\[\begin{aligned} -t_{max}&g_i}t_i(x_i-g_i) \\ -t_{max}&< -t_at_{max} + \sum_{x_i>g_i}t_{max}(x_i-g_i) \\ -1&< -t_a + \sum_{x_i>g_i}(x_i-g_i) \\ t_a-1&<\sum_{x_i>g_i}(x_i-g_i) \\ t_a&\le\sum_{x_i>g_i}(x_i-g_i) \end{aligned} \]

即 \(x\) 相较于 \(g\) 至少多取了 \(t_a\) 个物品。根据贪心结构，所有满足 \(x_i>g_i\) 的物品都排在 \(a\) 的后面，因此它们的性价比都满足 \(r_i\le r_a\)。

于是，在这些多取的物品中，由抽屉原理，可以选出一个非空子集 \(S\)（不妨考虑前缀和），使得

\[\sum_{i\in S}t_i\equiv0\pmod{t_a}. \]

设

\[\sum_{i\in S}t_i=q t_a. \]

由于 \(x_a，我们可以拿 \(S\) 中的物品换 \(q\) 个物品 \(a\)，从而

\(W(x)\) 单调不减
\(T(x)\) 不变
\(H(x)\) 单调减小

这与 \(x\) 是所有最优解中 \(H\) 最小者矛盾。

情况二：\(\exists a,x_a-g_a>t_{max}\)

这与情况一完全对称。

同理

\[\begin{aligned} & \Delta_{-}=\sum_{x_ig_i}t_i(x_i-g_i) \ge t_a(x_a-g_a)>t_at_{max} \end{aligned} \]

有

\[\begin{aligned} T(x)-T(g) &< t_{max} \\ \Delta_{-}+\Delta_{+} &< t_{max} \\ \sum_{x_ig_i}t_i(x_i-g_i) &< t_{max} \\ \sum_{x_i

即至少少选 \(t_a\) 个物品，少选的物品必排在 \(a\) 前面。后面的论证同理。

证毕。