大箱子装小箱子的体积计算

Question

一个100 * 100 * 100的大箱子，装若干个各种不同规格的矩形小箱子（知道小箱子的长宽高），怎么计算大箱子是否能够装下这若干个小箱子？程序上应该以什么思路去思考计算？

实际中就是仓库有箱子装货，需要计算以最优化的存放方式，新增的货物能否装进集装箱

Answer 1

感觉类似动态规划背包问题求最优解，只不过是三个维度了，要复杂一些。

Answer 2

类似的问题我以前思考过. 仅说说我自己的想法, 应该还有更好的 解法吧.

比如一开始是 100 * 100 * 100的空间, 现在放入一个 10 * 20 * 30 的箱子. 剩下的空间你可以 把它再分为 三个 尽可能大的 长方体. 可能的划分方案有 六种, 其中两种应该是:
100 * 100 * 90, 10 * 80 *100, 10 * 20 * 70
100 * 100 * 90, 10 * 70 *100, 10 * 30 * 80
对下一个箱子 重复以上过程.

我觉得自己的想法应该是对的, 但也没有去证明 :)
另外 涉及到 空间的想象, 可能比较难理解一些. 而且 这里随着 箱子的数量, 划分的空间 呈指数级 增加.

Answer 3

随便画画，欢迎拍砖。