容量为 11目标是把所有物品放进若干箱子使得每个箱子内物品大小之和不超过 11并最小化箱子数量。这个问题很适合讲近似算法。它足够简单简单到你可以在十分钟内写出好几个贪心版本但它也足够刁钻刁钻到“看起来很合理”的策略会在某些输入上稳定翻车。这是一个 NP-hard 问题严格地说优化版本的 Bin Packing 是 NP-hard对应的判定版本是给定物品大小和整数 BB是否能用不超过 BB 个箱子装下所有物品这个判定版本属于 NP因为验证答案显然很简单。而证明 NP-hard 可以从 Partition 问题归约。Partition 的输入是一组正整数 a1,a2,…,ana1​,a2​,…,an​它们的总和为 2T2T问题是能否选出一部分数使其和恰好为 TT。已知这个问题是 NP-hard。把每个整数 aiai​ 变成一个物品容量设为 TT问能不能用 22 个箱子装下所有物品。这个构造和原问题等价如果存在一个和为 TT 的子集就把这个子集放进第一个箱子剩下的总和也是 TT放进第二个箱子反过来如果所有物品能放进两个容量为 TT 的箱子由于总大小是 2T2T两个箱子都必须刚好装满于是其中一个箱子里的物品就对应一个和为 TT 的子集。即 Partition 可以平凡地归约为 K2K2 的 Bin Packing它说明 Bin Packing 至少是弱 NP-hard。而更深一步通过 3-Partition 归约还可以证明 Bin Packing 是强 NP-hard。Next Fit只记住当前箱子的贪心对这样一个最小化问题近似比通常写成 A(I)≤ρ⋅OPT(I)A(I)≤ρ⋅OPT(I)其中 A(I)A(I) 是算法求出的解OPT(I)OPT(I) 是最理论优解。Next Fit 是最简单的在线算法。它只维护当前正在使用的箱子新物品来了如果能放进当前箱子就放进去如果放不进去就关闭当前箱子打开一个新箱子。它的实现几乎不需要数据结构扫描一遍即可时间复杂度 O(n)O(n)额外空间也很低。问题在于它一旦关闭某个箱子就再也不会回头看。对输入 0.51,0.51,0.49,0.490.51,0.51,0.49,0.49Next Fit 会先把第一个 0.510.51 放进第一个箱子第二个 0.510.51 放不进去于是开第二个箱子随后 0.490.49 可以放进第二个箱子使第二个箱子刚好满最后一个 0.490.49 又只能开第三个箱子。它用了 33 个箱子而最优只需要 22 个。不过 Next Fit 并不是完全没有理论保证。可以证明 A(I)≤2OPT(I)−1A(I)≤2OPT(I)−1。每次开新箱子说明当前物品放不进上一个箱子因此相邻两个箱子的装载量之和会超过 11。把箱子两两配对就能得到算法使用的箱子数不会超过最优解的大约两倍。当然这个界也太粗太宽了。First Fit 和 Best Fit重新利用旧箱子First Fit 比 Next Fit 多做了一件事新物品到来时从前往后扫描已有箱子把它放进第一个能容纳它的箱子如果没有箱子能放下才打开新箱子。Best Fit 则换了一个选择标准把物品放入能够容纳它且剩余空间最小的箱子尽量把某个箱子填紧。这两个算法都可以在线运行因为它们不需要提前知道未来物品。用平衡树或 multiset 维护剩余容量每次找不小于当前物品大小的剩余空间可以找最小的然后更新该箱子的剩余容量整体可以做到 O(nlog⁡n)O(nlogn) 量级。从近似比看First Fit 和 Best Fit 的经典渐近近似比都是 1.71.7。也就是说可以认为它们在最坏情况下满足类似 A(I)≤1.7OPT(I)O(1)A(I)≤1.7OPT(I)O(1) 的比 Next Fit 的 22 好而“选择剩余最小的”也不会带来渐进性质的改善。不过这个证明要复杂得多。当然算法的实际表现通常比最坏情况好不会一直顶着上界。要构造较坏的例子思路是按顺序喂给算法几批尺寸层级不同的物品先给一批很小的物品再给稍大一点的物品让算法把早期开出的箱子填成一些看似还行、但剩余空间形状很差的状态随后再给中等物品和大物品使它们无法回填前面的空隙只能不断开新箱子。例如假设我们有 6n6n 个大小为 0.15 的物品 6n6n 个大小为 0.34 的物品以及 6n6n 个大小为 0.51 的物品。最优的装箱方法显然是将一个 0.15、一个 0.34 和一个 0.51 的物品放在一个箱子里因为它们加起来正好是 1。这样6n6n 个箱子就能装下所有物品。而First Fit的装箱过程处理 0.15 的物品First Fit 会将每 6 个 0.15 的物品放入一个箱子共使用 nn个箱子。每个箱子被占用 0.9 的空间无法再放入任何剩余物品。处理 0.34 的物品此时之前装 0.15 物品的箱子已经无法再放入东西因此 0.34 的物品只能放入新箱子。First Fit 会将每 2 个 0.34 的物品放入一个箱子共使用 3n3n 个新箱子。这些箱子占用 0.68 的空间也无法放入 0.51 的物品。处理 0.51 的物品前面的箱子都已无法再容纳任何物品因此每个 0.51 的物品都必须单独占用一个新箱子共使用 6n6n 个箱子。First Fit 总共使用的箱子数为 n3n6n10nn3n6n10n。因此其近似比为 10n6n536n10n​35​。First Fit 的实际最坏情况 1.7 比率构造思路类似但更加复杂。First Fit 受箱子顺序影响Best Fit 受“尽量填满”这个目标影响它们都没有真正理解未来会不会出现一批刚好能填补缝隙的小物品。在线算法无法预知未来这个限制不是实现技巧能消掉的。Decreasing排序改变了整个问题如果允许离线处理也就是所有物品一开始就已知一个自然改进是先按大小从大到小排序再运行 First Fit 或 Best Fit。这就得到 First Fit Decreasing简称 FFD以及 Best Fit Decreasing简称 BFD。排序的作用很朴素先处理大物品避免它们在后期无处可放。小物品更灵活可以用来填缝。这个思路在装箱问题里尤其有效因为大小超过 1/21/2 的物品每个都必须占据不同箱子大小超过 1/31/3 的物品每个箱子至多放两个。越大的物品越强地约束最终结构越应该早点决定位置。FFD 的经典保证是 A(I)≤119OPT(I)1A(I)≤911​OPT(I)1BFD 也有同阶的渐近保证。这个常数已经比在线贪心的 1.71.7 明显更好离最优解已经很近了而实现成本只是在原贪心前面加了一次排序。这个界限的证明非常非常难。需要将可能出现的物品大小组合划分成上百种不同的“模式”然后逐一分析装箱过程中“浪费”的空间。大物品限制了箱子的数量小物品填充了空隙。但小物品的排列组合方式极其多样必须证明最坏情况恰好发生在物品大小集中在 1/21/2 和 1/31/3 附近且这种组合造成的浪费刚好卡在 2/92/9 的空间上。算法是否在线典型实现复杂度近似保证Next Fit是O(n)O(n)不超过 2OPT−12OPT−1First Fit是朴素 O(nm)O(nm)可优化渐近比 1.71.7Best Fit是通常 O(nlog⁡n)O(nlogn)渐近比 1.71.7First Fit Decreasing否排序后贪心不超过 119OPT1911​OPT1Best Fit Decreasing否排序后贪心渐近比 11/911/9 级别总结缝隙和耐心这个具体的动作实际上可以抽象成一个困难的组合优化问题。Next Fit 像一个没有耐心的人只看眼前的箱子First Fit 和 Best Fit 愿意回头翻旧箱子但仍然被输入顺序牵着走FFD 和 BFD 先把大块头安排好再让小物品填补缝隙于是一下子跨过了很多坏情况。他们都是贪心算法虽然得不到最优解但经过思路优化已经有很近的界限了。