寻找最佳三维箱尺寸的一组三维矩形项 [英] Finding the optimal 3D box sizes for a group of 3D rectangular items

问题描述

当我说中我说的是航运箱。

When I say box I am talking about shipping boxes.

我有一些我需要装入的几箱地随机大小，小件物品。 我需要知道哪些箱尺寸是最优的。

I have a number of random sized, small items that I need to pack into as few boxes as possible. I need to know what box sizes are optimal.

• 所有项目都是直角棱镜。
• 可以很容易地排除一个盒子大小是太大，不适合的项目。
• 我知道箱尺寸（他们是可用的箱尺寸，我有存货）
• 产品可以水平或垂直放置，不斜。
可用于
• 在多达箱按要求。我们的目标是使用尽可能少的拖曳尽可能。
• 多个箱尺寸可以用于最佳地适应不同尺寸的物品。

• All items are rectangular prisms.
• It's easy to exclude a box size for an item which is too large to fit.
• I know the box sizes (they are the available box sizes which I have in-stock)
• Items can be positioned horizontally or vertically, not diagonal.
• As many boxes as required can be used. The goal is to use as few boxes as possible.
• Multiple box sizes may be used to optimally fit the varying-sized items.

什么算法存在，让我算算，我需要使用的最佳空间使用箱尺寸？ 要适应大多数项目进入的几箱地。

What algorithm exists that allows me to calculate the box sizes I need to use for optimal space usage? To fit the most items into as few boxes as possible.

可用箱尺寸来自我有什么用，有存货。您可以创建由箱尺寸有限数量的用于举例的目的。

The available box sizes come from what I have available, in-stock. You can create a finite number of made up box sizes for example purposes.

推荐答案

这是装箱的推广问题的，这意味着它是一个NP难。

This is a generalization of the Bin packing problem, meaning it is NP-Hard.

要看到这一点，想象到的所有箱子和包具有相同的宽度和高度，此外，所有箱（但不包）具有相同的长度。然后，它是一个一维的问题：我们有规模的V箱，和包大小的<子> 1 ，一个 ₂ ，...，A <子> N 。这个简单的情况下，正是装箱问题。因此，快速解决您的问题，为我们提供了一个快速的解决方案，装箱，所以你的问题是，至少在硬;并且由于装箱是NP难的，所以你的问题。

To see this, imagine all bins and packages have the same width and height, and additionally all bins (but not packages) have the same length. Then it is a one-dimensional problem: we have bins of size V, and packages of size a₁, a₂, ..., a_n. This simplified case is exactly the Bin-packing problem. Thus, a fast solution to your problem gives us a fast solution to bin-packing, so your problem is at least as hard; and since bin-packing is NP-Hard, so is your problem.

有可虽然有些近似算法;例如，可以很容易地表明，简单的首次适应算法的 （把每一个项目，它适合进入第一仓）的决不会做不如2倍的最佳解决方案。

There are some approximation algorithms available though; for example, it's easy to show that the simple first-fit algorithm (put every item in the first bin that it fits into) will never do worse than 2x the optimal solution.

类似的第一飞度减少算法的（降序排列的项目，然后把每一个项目在它适合进入第一仓）的是更好的，保证是在约25％的最优解。也有另一种，稍微更复杂的算法称为 MFFD 的这保证是在大约20％的

The similar "First Fit Decreasing" algorithm (sort the items in descending order, then put every item in the first bin it fits into) is even better, guaranteeing to be within about 25% of the optimal solution. There is also another, slightly more complicated algorithm called MFFD which guarantees to be within about 20%.

当然，只有7箱，你可以永远只是蛮力强行解决方案。这将需要约7 ^N 步骤的（其中 N 是项目数）的，所以这个解决方案是不可行的同十几个左右的项目更多。

And of course, with only 7 boxes, you could always just brute-force the solution. This will require about 7ⁿ steps (where n is the number of items), so this solution is infeasible with more than a dozen or so items.

这篇关于寻找最佳三维箱尺寸的一组三维矩形项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！