装箱问题

装箱问题（bin packing problem）把给定物品全部放进容量相同的箱子，要求使用的箱子最少。每件物品不可拆分，箱内总大小不能超过容量。一维装箱只追踪一个可相加的资源；二维矩形排版还涉及形状、旋转及不重叠约束，不能只凭面积和直接套用一维模型。

有六件大小为 $6,5,3,2,2,2$ 的物品，箱容量十。总大小二十，任何方案至少需两箱。若把六和三先放一箱、五和两个二放一箱，最后一个二将不得不单独开箱；而改成 $(6,2,2)$ 与 $(5,3,2)$ 就刚好两箱。安排顺序造成的零碎空间，可能比总体容量更关键。

归箱模型与容量下界

对 $n$ 件物品，容量 $B>0$，大小满足 $0<s_i\le B$。至多开 $n$ 个箱；二元变量 $x_{ij}$ 表示物品归箱，$y_j$ 表示开箱： $$\begin{array}{cc}min& \sum _{j=1}^n{y}_j,\\ \sum _j{x}_{ij}& =1,\\ \sum _i{s}_i{x}_{ij}& \le B{y}_j,x_{ij}\le y_j.\end{array}$$ 变量均为零一。将容量约束相加，立即得到体积下界 $$\mathrm{O}\mathrm{P}\mathrm{T}\ge \lceil \frac{\sum _i{s}_i}{B}\rceil .$$ 主例下界二，与明确构造的两箱方案一致，因此无需继续搜索即可确认最优。体积下界并不总能达到，例如三个大小六的物品、容量十，每箱只能放一件，实际需三箱而下界仅二。

每条横框容量十；灰色空段是未用空间。上方是可行启发式，下方是达到容量下界的最优证书。

首次适应递减及不变量

首次适应算法依次处理物品：检查已有箱子，放入第一个还有足够空间的箱；都放不下才新开箱。先按大小递减排序后执行，称首次适应递减（FFD）。每次只在剩余容量足够时放入，故“已装物品各出现一次且每箱未超容”始终保持；最终得到可行上界，不保证恰好最优。

下面返回每箱的原物品下标，以便区分大小相同的不同物品。输入只接受正整数大小及整数容量，空物品表返回空箱列表。

Python 3

def first_fit_decreasing(sizes, capacity):
    s = tuple(sizes)
    if type(capacity) is not int or capacity <= 0:
        raise ValueError("positive integer capacity required")
    if any(type(x) is not int or not 0 < x <= capacity for x in s):
        raise ValueError("positive integer sizes no larger than capacity required")
    bins, free = [], []
    for i in sorted(range(len(s)), key=lambda i: (-s[i], i)):
        for j in range(len(bins)):
            if s[i] <= free[j]:
                bins[j].append(i); free[j] -= s[i]
                break
        else:
            bins.append([i]); free.append(capacity-s[i])
    return bins

sizes = [6,5,3,2,2,2]
print([[sizes[i] for i in b] for b in first_fit_decreasing(sizes,10)])
# [[6, 3], [5, 2, 2], [2]]

排序需 $O(n\log n)$，逐物品扫描至多 $n$ 箱使总时间为 $O(n^2)$，保存箱内下标及剩余容量需 $O(n)$ 空间。

还能给首次适应一个保守但完整的保证。设最后用了 $m\ge 2$ 个箱，任取前后两箱。后箱的第一件物品当时放不进前箱，所以前箱当时的装载加该件大小大于 $B$；最终两箱装载之和更大于 $B$。对全部箱对求和，每箱载重出现 $m-1$ 次，因此 $$\begin{array}{cc}(m-1)\sum _i{s}_i& >(\genfrac{}{}{0ex}{}{m}{2})B,\\ m& <\frac{2\sum _i{s}_i}{B}\le 2\mathrm{O}\mathrm{P}\mathrm{T}.\end{array}$$ 整数性给 $m\le 2\mathrm{O}\mathrm{P}\mathrm{T}-1$。一箱情形也满足此界。这条较粗保证不需要排序，当然也适用于FFD；它不是FFD所能达到的最精细理论界。

变式。 三件大小六、容量十时，FFD和最优都用三箱。若一个物品大于容量，模型不可行，代码会明确拒绝；不能让算法自动开一个超容量箱子来掩盖数据错误。固定箱数后只挑收益最大的部分物品，属于多背包问题，目标与“全部装完、最少开箱”不同。