为一组三维矩形物品寻找最佳的三维盒子尺寸

Question

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

我有许多随意大小的小物品需要尽可能少地装入箱子中。 我需要知道哪些箱子尺寸最优。

• 所有物品都是长方体。
• 可以轻松排除太大而无法适合的物品的箱子尺寸。
• 我知道箱子尺寸（它们是我库存中可用的箱子尺寸）
• 物品可以水平或垂直放置，不能对角线放置。
• 可以使用所需数量的箱子。目标是使用尽可能少的箱子。
• 可以使用多个箱子尺寸来最佳地适应不同大小的物品。

存在什么算法可以让我计算出需要使用的箱子尺寸以实现最佳空间利用率？尽量将最多的物品装入尽可能少的箱子中。

可用的箱子尺寸来自我库存中可用的尺寸。您可以为示例目的创建有限数量的虚构箱子尺寸。

- unixman83

---

这只涉及到2个维度吗？长度和宽度？ - Francis P

这听起来很像是“背包问题”，它是“NP-完全”的。你可以看一下近似“背包问题”的算法，看看是否能够将其调整为符合你的需求。 - twain249

@FrancisP 立方体，长度，宽度和高度。我不知道一个立方长方形的技术术语。 - unixman83

@FrancisP 这个词只是长方体。我已经编辑过了。 - twain249

那你是怎么解决的？PHP 中有没有现成的类或代码可以使用？有什么想法吗？自己编写一个需要好几天时间！ - John

Answer 1

这是装箱问题的概括，意味着它是NP难问题。假设所有箱子和包裹都具有相同的宽度和高度，并且所有箱子（但不是包裹）都具有相同的长度，则这是一个一维问题：我们有尺寸为V的箱子和尺寸为a₁、a₂、...、a_n的包裹。这种简化情况正是装箱问题。因此，解决你的问题能够快速解决装箱问题，所以你的问题至少与装箱问题同样困难；而由于装箱问题是NP难问题，所以你的问题也是NP难问题。

---

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

类似的“首次递减拟合”算法 (按降序排列物品，然后将每个物品放入它适合的第一个箱子中) 更好，保证在最优解的约25%之内。还有另一个稍微复杂一些的算法称为MFFD，保证在最优解的约20%之内。

当然，对于只有7个箱子的情况，您可以直接暴力求解。这将需要大约7ⁿ步骤 (其中n是物品的数量)，因此该解决方案在超过十几个物品时是不可行的。

- BlueRaja - Danny Pflughoeft

---

我的问题是，我选择的箱子大小部分基于物品的总体积。例如：许多小物品用大型UPS箱比使用许多小型USPS平邮盒更便宜。也就是说，随着总体积的增加，使用较大的箱子通常会更好。 - unixman83

@unixman83：-_- 这个问题提到的是将物品放进最少的盒子，没有提到价值。我认为你会发现你的新问题是背包问题的一种推广，因此你仍然无法找到最优解:\尝试查找一些背包近似算法。 - BlueRaja - Danny Pflughoeft

是的，谢谢您回答了我遇到的空间匹配问题。这绝对是帮助。 - unixman83

Answer 2

您描述了 背包问题 的一个变体。请查看维基百科文章以获取更多有关该问题的方法的详细信息，这里无法提供更多信息。

- Michael Slade

---

作为“背包问题的变体”，并不意味着它是NP完全问题。 - BlueRaja - Danny Pflughoeft

嘿，我并没有说它是NP完全问题！但你可以写整整一本书来讲述这个主题，而我不想试图用100个字或更少的字来概括它。 - Michael Slade

这个回答不应该得到0分的评价。虽然它没有回答我提出的问题，但它可能是我所面临的问题更完整的答案。 - unixman83