algorithm - 为一组 3D 矩形项目找到最佳 3D 框尺寸

Question

当我说盒子时，我指的是装运箱。

我有一些随机大小的小元素，我需要将它们装入尽可能少的盒子中。我需要知道什么盒子尺寸是最佳的。

• 所有项目都是 rectangular prisms .
• 很容易为太大而不适合的商品排除盒子尺寸。
• 我知道盒子尺寸(它们是我有库存的可用盒子尺寸)
• 项目可以水平或垂直放置，而不是对角线放置。
• 可以使用所需数量的盒子。目标是使用尽可能少的盒子。
• 可以使用多种尺寸的盒子来最佳地适应不同尺寸的元素。

有什么算法可以让我计算为实现最佳空间使用而需要使用的框大小？ 将最多的元素放入尽可能少的盒子中。

可用的盒子尺寸来 self 现有的库存。出于示例目的，您可以创建有限数量的组合框尺寸。

Answer 1

这是 Bin packing problem 的概括，表示它是 NP-Hard。

为了理解这一点，假设所有箱子和包裹的宽度和高度都相同，而且所有箱子(但包裹除外)的长度也相同。那么这是一个一维问题:我们有大小为 V 的箱子，以及大小为 a₁, a₂, ..., a_{n 。这个简化的案例就是 Bin-packing 问题。因此，快速解决您的问题为我们提供了快速解决装箱问题的方法，因此您的问题至少同样困难；由于装箱是 NP-Hard，因此您的问题也是如此。}

---

虽然有一些近似算法可用；例如，很容易证明简单的 first-fit算法(将每个项目放入它适合的第一个容器中)永远不会比最优解的 2 倍差。

类似的“首次适合递减”算法(按降序排列项目，然后将每个项目放入它适合的第一个容器中)甚至更好，保证在大约 25% 的范围内最优解。还有另一种稍微复杂的算法，称为 MFFD。这保证在大约 20% 以内。

当然，只有 7 个盒子，您总是可以通过暴力破解解决方案。这将需要大约 7ⁿ 个步骤(其中 n 是项目的数量)，因此对于十几个左右的项目，此解决方案是不可行的。