问题
设给定 N 件物品，大小为 s1, s2, ..., sn,所有的大小都满足 0 ≤ si ≤ 1。问题是要把这些物品装到最小数目的箱子中，已知每个箱子的容量是 1 个单位。
有两种版本的装箱问题。第一种是联机(on-line)装箱问题。在这种问题中，必须将每一件物品放入一个箱子之后才处理下一件物品。第二种是脱机(off-line)装箱问题。在一个脱机装箱算法中，我们做任何事都需要等到所有的输入数据全被读入之后才进行。
联机问题
联机算法
联机算法从不知道输入何时会结束，因此它提供的任何性能保证必须在整个算法的每一时刻成立。
定理：存在使得任意联机装箱算法至少使用 最优箱子数的输入。
下项适合算法
当处理任何一件物品时，我们检查看它是否还能装进物品的同一个箱子中。如果能装进去，那么就把它放入该箱子中；否则，就开辟一个新的箱子。
定理: 令 M 是将一列物品 I 装箱所需的最优装箱数，则下项适合算法所用箱数绝不会超过 2M 个箱子。存在一些顺序使得下项适合算法用箱 2M-2 个。
首次适合算法
首次适合算法(first fit)算法的策略是依序扫描这些箱子但把新的一件物品放入足以盛下它的第一个箱子中。因此，只有当前放置物品的箱子已经没有再容下当前物品余地的时候，我们才开辟一个新箱子。
在任意时刻最多只有一个箱子其空出的部分大于箱子的一般，因为若有第二个这样的箱子，则它装的物品就会装到第一个这样的箱子中了。因此我们可以断言：首次适合算法保证其解最多包含最优箱数的二倍。
定理：令 M 是将一列物品 I 装箱所需要的最优箱子数，则首次适合算法使用的箱子数绝不多于 。存在使得首次适合算法使用
个箱子的顺序。
当首次适合算法对大量其大小均匀分布在 0 和 1 之间的物品进行运算时，经验结果指出，首次适合算法用到大约比最优装箱方法多 2% 的箱子。在许多情况下，这是完全可以接受的。
最佳适合算法
最佳适合算法与首次适合算法类似，但不是把一件新物品放入所发现的第一个能够容纳它的箱子，而是放到所有箱子中能够容纳它的最满的箱子中。
最佳适合算法比起最优算法，绝不会坏过 1.7 倍左右，而且存在一些输入，对于这些输入该算法（几乎）达到这个界限。不过，最佳适合算法编程还是简单的，特别是当需要 算法的时候，而且该算法对随机的输入确实表现得更好。
脱机算法
所有联机算法的主要问题在于将大件物品装箱困难，特别是当它们在输入的晚期出现的时候，围绕这个问题的自然方法是将各项排序，把最大的物品放在最先。此时可以应用首次适合算法或最佳适合算法，分别得到首次适合递减算法(fitst fit decreasing)和最佳适合递减算法(best fit decreasing)。
引理
- 令 N 项物品的输入大小（以递减顺序排序）分别为 s1,s2,...,sn，并设最优装箱方法使用 M 个箱子，那么，首次适合递减算法放到外加的箱子中的所有物品的大小最多为
。
- 放入外加箱子中的物品的个数最多是 M-1 。
定理
- 令 M 是将物品集 I 装箱所需的最优箱子数，则首次适合递减算法所用箱子数绝不超过
。
- 令 M 是将物品集 I 集装箱所需的最优箱子数，则首次适合递减算法所用箱子数绝不超过
。此外，存在使得首次适合递减算法用到
个箱子的序列。
