简介

把一些箱子装入容器中是一个在工业生产中经常遇到的数学难题，比如集装箱的装箱问题。装箱问题（Bin Packing）是一个经典的组合优化问题，有着广泛的应用，在日常生活中也屡见不鲜。

定义

设有许多具有同样结构和负荷的箱子 B1，B2，… ，其数量足够供所达到目的之用。每个箱子的负荷（可为长度、重量等等.）为 C ，今有 n 个负荷为 wj，0 < wj < C ， j = 1，2，…，n 的物品 J1，J2，…，Jn 需要装入箱内。装箱问题就是指寻找一种方法，使得能以最小数量的箱子数将J1，J2，…，Jn 全部装入箱内。

分类

装箱问题可分为一维装箱问题，二维装箱问题，三维装箱问题三种。现实生活中常见的应该是三维装箱问题。

根据目标的不同,三维装箱问题可分成以下几类：

箱柜装载问题(three-dimensional bin packing problem，简称3D-BPP)：给定一些不同类型的方型箱子和一些规格统一的方型容器，问题是要把所有箱子装入最少数量的容器中。

容器装载问题(three-dimensional container-packing problems，简称3D-CPP)：在该问题中，所有箱子要装入一个不限尺寸的容器中，目标是要找一个装填，使得容器体积最小。

背包装载问题(three-dimensional knapsack loading problems，简称3D-KLP)：每个箱子有一定的价值，背包装载是选择箱子的一部分装入容器中，使得装入容器中的箱子总价值最大。如果把箱子的体积作为价值，则目标转化为使容器浪费的体积最小。