多重背包的贪心近似定理

1. 问题描述

考虑标准的多重背包问题。有 \(n\) 种物品，第 \(i\) 种物品有 \(c_i\) 个，每个物品体积 \(t_i\)，价值 \(w_i\)，背包容量为 \(m\)。其中 \(n,c_i,t_i,w_i,m\) 均为正整数。

一个解记为长 \(n\) 的非负整数序列 \(s=\{s_1,s_2,\dots,s_n\}\)，其中 \(s_i\) 表示取了 \(s_i\) 个第 \(i\) 种物品，满足 \(0\le s_i\le c_i\) 且 \(\sum_is_it_i\le m\)。

定义解 \(s\) 的总体积和总价值分别为

\[T(s)=\sum_i s_i t_i \qquad W(s)=\sum_i s_i w_i \]

记第 \(i\) 种物品的性价比为 \(r_i=w_i/t_i\)。

记 \(t_{max}=\max_i t_i\)。

设所有最优解组成的集合为 \(O=\{s|s~\text{是一个最优解}\}\)。

现在按性价比 \(r_i\) 从高到低排序，尽可能多地装入物品，得到贪心解 \(g\)。

2. 贪心近似定理

我们要证明如下结论：

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

也就是说，一定存在一个最优解，它每一种物品取的数量都不会与贪心解相差超过 \(t_{max}\)。

3. 证明

3.1 准备

如果所有物品都可以全部装入背包，贪心解就是唯一最优解，定理显然成立。

因此下面统一假设 \(\sum_{i=1}^n c_i t_i>m\)，于是任何可行解都不会取完所有物品。这个性质将在后面使用。

记

\[H(s)=\sum_i|g_i-s_i|. \]

固定 \(x\) 为所有最优解中 \(H\) 最小的。我们将证明 \(x\) 满足 \(\forall i,|g_i-x_i|\le t_{max}\)。

3.2 贪心解的结构

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

由于物品无法全部装下，由贪心过程可知存在唯一的 \(k\)，使得

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

即：

性价比高于第 \(k\) 中物品的全取完
第 \(k\) 种物品取了一部分
第 \(k\) 种之后的物品不取

3.3 引理一

\(\forall s\in O\)，有

\[m-T(s)

证明：反设 \(\exists s\in O\) 满足 \(m-T(s)\ge t_{max}\)，即剩余容量至少还能装一个物品。由于物品不能全部取完，加入一个没取的物品能得到严格更优的解，矛盾。

3.4 引理二

\(\forall s\in O\)，有

\[-t_{max}

证明：显然 \(g\) 满足 \(m-T(g)。由引理一得 \(m-T(s)。结合两式即可证明。

3.5 反证法证明

反设存在 \(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\) 前面。后面的论证同理。

证毕。

4. 应用

在上面的多重背包问题中，我们令数据范围 \(n,t_i\le 100,m,c_i,w_i\le 10^9\)。

首先不难求出 \(g\)。由贪心近似定理，对于每一种物品 \(i\)，可以限制最优解 \(x_i\) 的范围：

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

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

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