为一组3D矩形项找到最佳3D盒尺寸

Question

当我说框时,我说的是运输箱.

我有一些随机大小的小物品,我需要装入尽可能少的箱子.我需要知道什么样的盒子尺寸是最佳的.

• 所有物品都是矩形棱镜.
• 对于太大而无法容纳的项目,可以轻松排除框大小.
• 我知道盒子尺寸(它们是我有库存的可用盒子尺寸)
• 物品可以水平或垂直放置,而不是对角线.
• 可以使用所需的多个盒子.目标是使用尽可能少的盒子.
• 可以使用多个盒子尺寸来最佳地适合不同尺寸的物品.

存在什么算法允许我计算我需要用于最佳空间使用的盒子大小？将大多数物品放入尽可能少的箱子中.

可用的盒子尺寸来自我现有的库存.出于示例目的,您可以创建有限数量的组合盒尺寸.

Answer 1

这是Bin打包问题的概括,意味着它是NP-Hard.

要想看到这一点,想象所有的箱子和包装都有相同的宽度和高度,另外所有的箱子(但不是包裹)都有相同的长度.那么这是一个一维问题:我们有大小为V的箱子,大小为₁,a ₂,......,a _n的包裹.这个简化的案例正是Bin-packing问题.因此,快速解决您的问题可以为我们提供快速的装箱解决方案,因此您的问题至少同样困难; 因为bin-packing是NP-Hard,所以你的问题也是如此.

但是有一些近似算法可用; 例如,很容易证明简单的首次拟合算法(将每个项目放在它适合的第一个bin中)绝不会比最佳解决方案的2 倍差.

类似的"首次适应减少"算法(降序对项目进行排序,然后把每一个项目在它适合进入第一仓)是更好的,保证是内最优解的约25%.还有另一种稍微复杂的算法称为MFFD,它保证在20%左右.

当然,只有7个盒子,你可以随便蛮力解决方案.这将需要大约7 ^n个步骤(n项目数量在哪里),因此这个解决方案是不可行的,有十几个项目.