PACT 07/07 装箱问题

Posted on 2020-07-11 Views:

定义

输入：件物品，第件物品的大小为 $a_i\in(0,1]$ 。

目标：将所有物品装进若干个大小为的箱内，并使所用的箱最少。

见缝插针算法（First-fit）

（总觉得自己的这个翻译有些问题……又似乎觉得没有问题……还是觉得有些问题？“首次适应”看起来太傻了，“先到先得”看起来又不大对劲……）

我们可以很暴力地设计一个算法：

将所有物品任意排列。
依次处理每一个物品，如果已经用的箱子里有一个还装得下就装进去，否则就新开一个箱子装进去。

这个算法被称为first-fit algorithm，我将其翻译为见缝插针算法。

这个算法是不是太粗暴了一点？其实可以证明，这个算法是一个倍近似算法。

引理：我们最终的打包方案当中，至多只有一个箱子是最多半满的（即在里面物品的体积 $\le \frac{1}{2}$ ）。

证明：考虑反证：如果有两个箱子都是最多半满，显然后开的那个箱子里的东西在算法运行的时候可以被塞进另外一个箱子里，就产生了矛盾。

假设我们的算法用了个箱子，因为忽略可能有的一个半满的箱子，剩下的箱子里物品的大小都 $>\frac{1}{2}$ ，显然有

$\frac{B-1}{2} < \sum_{i=1}^n a_i$

因此

$B < 2\sum_{i=1}^na_i + 1 \Rightarrow B\le 2\sum_{i=1}^na_i$

又因为最优方案所用箱子的总大小一定不小于物品的大小之和，

$\sum_{i=1}^n a_i \le \mathrm{OPT} \Rightarrow B\le 2\cdot \mathrm{OPT}$

PTAS设计

定理：对于任意的 $\varepsilon \in \left(0,\frac{1}{2}\right]$ ，我们都能设计一个 $(1+2\varepsilon)$ 倍的近似算法。

在证明这个定理之前，我们不妨思考一下：什么时候暴力搜索是可以接受的？

如果我们知道每个箱子最多装件物品，物品的大小只有种，那么对于一个箱子至多有几种装箱（装到放不下任何其他物品）的方案？运用一点组合数学的知识，不难得出答案是

$\binom{m + k-1}{m}$

不妨这个方案数为

，假设我们有

个箱子，最多有几种装箱的方案呢？

$\binom{n+R-1}{R-1} = \mathcal{O}\left(n^{R-1}\right)$

如果

不是常数，那么显然暴力枚举算法的复杂度是指数级的。

而如果是一个比较小的常数，也就是说 m, k 都是比较小的常数的话，暴力搜索的时间复杂度就是多项式级别的。

如何确保比较小？只要每件物品足够大就行了，于是我们把输入的物品分为

$a_i<\varepsilon$ 的小物品，
和 $a_i\ge \varepsilon$ 的大物品。

我们暂时先不管小物品。如何设计一个放大物品的 $(1+\varepsilon)$ 倍近似算法呢？

由定义，每件大物品大小 $>\varepsilon$ ，因此每个箱子能够放的大物品数目 $m<\frac{1}{\varepsilon}$ ，如果我们想要用暴力，只要再把限制住就行了。

为此，我们将所有物品按大小升序（或者说不降）排序，然后将排完的物品分成组，除了最后一组，每一组都有 $\lceil n/k \rceil$ 个物品。

假设我们现在的要处理的问题实例为，我们创建一个新实例，其中每一个物品的大小被高估为它所在组最大物品的大小：

很显然，因为做的时候我们高估了物品的大小，也就是让问题更难了，每个的解都是的可行解。而当中物品的大小只有种，加上的限制，是可以暴力解决的。我们可以暴力把解出来，然后套到上面作为我们算法的解。但是如何分析呢？或者说，如何用的最优解来给我们的最优解一个上界呢？

出于分析的目的，我们再考虑另一个问题实例，其中每一个物品的大小被低估为它所在组最小物品的大小：

类似地，我们可以得出：每一个的可行解一定是的一个可行解，反之未必然，即

$\mathrm{OPT}_{J'} \le \mathrm{OPT}_{I}$

现在思考一个问题：如果我们有一组

的最优解，如何把它尽可能地转换成一组

的可行解呢？

一个方案是让的每个物品对应当中更大一组中的物品，然后就按照最优解的方式装箱，这样除了最大的一组以外中的所有物品都有办法装箱了。令最大的那一组不知道怎么装箱的物品集合为。

因为对于里面的物品我们大不了一个箱子装一个，因此我们得到

$\mathrm{OPT}_{J} \le \mathrm{OPT}_{J'}+|Q| \le \mathrm{OPT}_{I} + \left\lceil\frac{n}{k}\right\rceil$

注意因为我们是暴力解

的，现在不等式的左边 $\mathrm{OPT}_J$ 就是我们算法的代价。为了证明近似比，我们希望上面不等式的右边变成一个 $(1+\varepsilon)\mathrm{OPT}_I$ 。

注意到在这个只有大物品的问题当中， $\mathrm{OPT}_I \ge \lceil n\cdot \varepsilon \rceil$ ，因此，若令 $k=\left\lceil\frac{1}{\varepsilon^2}\right\rceil$ 。上面的分析就变成了

$\begin{aligned} \mathrm{OPT}_{J} &\le \mathrm{OPT}_{I} + \left\lceil\frac{n}{k}\right\rceil \\ &\le \mathrm{OPT}_{I} + \left\lceil n \cdot \varepsilon^2\right\rceil \\ &\le \mathrm{OPT}_{I} + \varepsilon\left\lfloor n \cdot \varepsilon\right\rfloor + 1 \\ &\le \mathrm{OPT}_{I} + \varepsilon\mathrm{OPT}_{I}+1 \\ &= (1+\varepsilon)\mathrm{OPT}_{I} +1 \end{aligned}$

我们就证明了我们装大物品的近似比是 $(1+\varepsilon)$ 。注意到这个多出来的

虽然让人不爽，但是在渐进意义下是可以忽略的。但是因为毕竟是在渐渐意义下，我们刚刚的算法不能被称为PTAS了，而是APTAS（Asymptotic PTAS）。（这个

也不是没有办法去掉，只是如果要去掉那

的表达式可能要复杂一点）

接下来再处理小物品：我们现在对于大物品已经有了一个渐进近似比为 $(1+\varepsilon)$ 的算法，我们如何在这个算法的解的基础上尽可能优地把小物品加进去呢？我们不妨使用见缝插针的策略。我们分析一下这样的效果：

如果我们使用见缝插针算法装小物品不需要开新的箱子，那么箱子数不变，我们的算法总体来说渐进近似比还是 $(1+\varepsilon)$ 。
如果我们开了新的箱子。我们可以证明：在我们方案中，至多有一个箱子，其里面物品的大小总和不大于 $(1-\varepsilon)$ ，且这个箱子一定是在装小物品的时候新开的。证明方式和之前分析见缝插针算法的时候是类似的：如果有两个 $(1-\varepsilon)$ 满的箱子，那么后开的那个箱子里面装的小物品一定可以塞进另外一个先前开的箱子里面，于是便产生了矛盾。我们分析一下这个情况下我们算法的近似比。假设我们的算法开了个箱子：

$\left.\begin{aligned} (B-1)(1-\varepsilon) < \sum_{i=1}^na_i \le \mathrm{OPT} \Rightarrow B\le \frac{\mathrm{OPT}}{1-\varepsilon} \\ \varepsilon \in \left(0,\frac{1}{2}\right] \Rightarrow \frac{1}{1-\varepsilon} = 1+2\varepsilon +\frac{\varepsilon(2\varepsilon-1)}{1-\varepsilon} \le 1+2\varepsilon \end{aligned} \right\} \Rightarrow B\le (1+2\varepsilon) \mathrm{OPT}$

综上，我们算法的渐进近似比是 $(1+2\varepsilon)$ 。

最后回顾一下我们的APTAS：

暂时忽略小物品。
设 $k=\left\lceil\frac{1}{\varepsilon^2}\right\rceil$ 并以此创建新实例。
暴力搜索求得的最优解。
把我们的最优解直接套到上面，得到大物品的装箱方案。
使用见缝插针法将小物品装箱。