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

B：关于新型三维装箱问题为 NP-hard 问题的证明
引理 B.1: 本文提出的新型三维装箱问题为 NP-hard 问题。
证明：首先，我们证明新型的二维装箱问题为 NP-hard 问题。为了完成此证明，我们将新型的二维装箱问题归约为一维的普通装箱问题。
对于一维的普通装箱问题，我们有n个物品，其尺寸分别为W_1, W_2, ..., W_n，其中每一个W_i为正整数。箱子的容量为正整数W。优化目标为最小化箱子的使用数量。
为了将新型的二维装箱问题归约为普通的一维装箱问题，我们假设有n个物品，其宽度分别为W_1, W_2, ..., W_n，高度为

。而且还有一个物品，其宽度为 W，高度为