[科普中国]-立方装箱：最优化解题的应用

装箱问题属于组合最优化问题，问题高度复杂，目前还没有确切的求解方法，只能运用启发式的方法解决，譬如构造式方法或近似方法等。装箱问题期望达到将有限数量的不同大小的物体装入箱中，同时最小化占用“箱”的空间。装箱问题在理论和实践上都具有很重要的意义，在理论上能够启发部分非常复杂的、非线性的系统最优化求解；在实践上能够将其广泛地应用于运输行业（货物装箱）与地图划分（停车场/公园划分）等实际问题中。

装箱问题分为一维装箱、二维装箱和三维装箱。一维装箱问题仅考虑一个因素，如质量、长度等；二维装箱问题通常考虑长与宽这两个因素；三维装箱问题通常考虑长、宽和高三个因素。

而立方装箱问题便是理想化的三维装箱问题，指的是某个特定的长方体箱子能否被有限数量且互异（即体积两两不等）的立方体填充且不留空隙；与此对应的是正方装箱问题，即理想化的二维装箱问题，一个特定的矩形能否被有限数量且互异（即面积两两不等）的正方形填充且不留空隙。

事实上，对第一个问题即立方装箱问题而言，答案是不可行的。对有限个大小各异的立方体而言，无论如何摆放，作为箱子的长方体总会留有空隙。

这一结论可以使用反证法得以证明。如果说一个长方体的箱子可以被有限个大小各异的立方体装满，那么体积最小的立方体周围绝对不会留有缝隙，但事实上，它总会与其他面形成一个凹槽，又因为箱子里的立方体大小各不相同，那么这个凹槽必然要用比它边长更小的立方体进行填充，这就与这个立方体体积最小的条件形成矛盾。因此，使用有限个大小各异的立方体无法将长方体箱子装满，这一结论与长方体箱子的长、宽、高无关。

现实中的三维装箱问题完全属于最优化问题，目的是使用给定的箱子填装长方体货物，使得箱子的使用量最小。这一问题现在通常用计算机算法完成而非仅仅依靠经验解决。

本作品为“科普中国-科学原理一点通”原创，转载时务请注明出处。