多重背包的贪心近似定理

· · 算法·理论

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 i<k, g_i=c_i\\ &0\le g_k<c_k\\ &\forall i>k, g_i=0 \\ \end{aligned}

即：

3.3. 引理一

$$ m-T(s)<t_{\max} $$ 证明：反设 $\exists s\in O$ 满足 $m-T(s)\ge t_{\max}$，即剩余容量至少还能装一个物品。由于物品不能全部取完，加入一个没取的物品能得到严格更优的解，矛盾。 ### 3.4. 引理二 $\forall s\in O$，有 $$ -t_{\max}<T(s)-T(g)<t_{\max} $$ 证明：显然 $g$ 满足 $m-T(g)<t_{\max}$。由引理一得 $m-T(s)<t_{\max}$。结合两式即可证明。 ### 3.5. 反证法证明 反设存在 $a$，使得 $|g_a-x_a|>t_{\max}$。分类讨论拆绝对值。 #### 情况一：$\exists a,g_a-x_a>t_{\max}

定义

\begin{aligned} & \Delta_{-} = \sum_{x_i<g_i}t_i(x_i-g_i) \le t_a(x_a-g_a) < -t_at_{\max} \\ & \Delta_{+} = \sum_{x_i>g_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}&<T(x)-T(g) \\ -t_{\max}&< \Delta_{-} + \Delta_{+} \\ -t_{\max}&< \sum_{x_i<g_i}t_i(x_i-g_i) + \sum_{x_i>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<g_a，我们可以拿 S 中的物品换 q 个物品 a，从而

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

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

这与情况一完全对称。

同理

\begin{aligned} & \Delta_{-}=\sum_{x_i<g_i}t_i(x_i-g_i) \ge \sum_{x_i<g_i}t_{\max}(x_i-g_i) \\ & \Delta_{+}=\sum_{x_i>g_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_i<g_i}t_i(x_i-g_i) + \sum_{x_i>g_i}t_i(x_i-g_i) &< t_{\max} \\ \sum_{x_i<g_i}t_{\max}(x_i-g_i) + t_at_{\max} &< t_{\max} \\ \sum_{x_i<g_i}(x_i-g_i) + t_a &< 1 \\ \sum_{x_i<g_i}(x_i-g_i) &< 1-t_a \\ \sum_{x_i<g_i}(x_i-g_i) &\le -t_a \\ \sum_{x_i<g_i}(g_i-x_i) &\ge t_a \\ \end{aligned}

即至少少选 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 即可。