阿里IJCAI2017Workshop论文：使用深度强化学习方法求解一类新型三维装箱问题(12)

，我们称此物品为基准物品。则可以定义一个新型的装箱问题为：找到一个能够装下所有n 1个物品且表面积最小的箱子。
不失一般性，我们假设基准物品放在箱子的左下角。如果将一个其它物品放到基准物品的右方，则至少会使表面积增加
。而如果将其它物品放到基准物品的上方，则最多使表面积增加 W。所以所有的物品必须被放到基准物品的上方。
然后，我们证明物品在放置时没有进行旋转。如果在放置时有任意一个物品进行了旋转，则表面积至少增加
。如果放置时没有物品进行旋转，则表面积至多增加W，所以为了最小化表面积，物品放置时是没有进行旋转的。
所以，如果我们能够针对此种包含n 1个物品的新型二维装箱问题找到一个最优解，则我们就能够同时获得对于普通一维装箱问题的最优解。即如果我们能够在多项式时间内求解此类新型二维装箱问题，则同样能够在多项式时间内求解以上的普通一维装箱问题。显然，这种情况不可能出现，除非 P=NP。
对于新型的三维装箱问题，我们可以同样在二维问题的基础上对每个物品增加一个长度

。证明方法与以上相同。