标签: bin-packing

有没有人知道现有的软件或算法来计算运送多件物品的包装尺寸？

我的库存数据库中有很多项目,定义了长度,宽度和高度尺寸.鉴于这些尺寸,我需要计算购买的商品中有多少符合预定义的尺寸.

stackoverflow上有一些类似的问题,但它们似乎都没有提供一个明确的答案,即没有对NP难题和算法有深刻理解的人可以理解.

如何执行矩形对象的2D bin打包？就我而言,我正在尝试将几个图像组合成一个图像,用作spritesheet,使用最小的空间.每个图像可能具有截然不同的边界,但容器没有设置边界.

我希望有人了解bin打包算法可以解释如何以编程方式实现这一点,而不是提供bin打包方法的一般概述.

我面临着一个三维装箱问题,目前正在进行一些初步研究,以确定哪些算法/启发式方法目前正在产生最佳结果.由于问题是NP难,我不希望在每种情况下找到最佳解决方案,但我想知道:

1)什么是最精确的求解器？分支和绑定？我可以通过合理的计算资源解决哪些问题实例大小？
2)什么是最好的启发式求解器？
3)进行一些实验有哪些现成的解决方案？

试图找出最好的方法，将装箱后的已知宽度的svg图像打包/分布在水平行中，如果容器的宽度太紧，可以将它们堆叠在一起。

容器的高度应最佳地自动调整，并且重力应为垂直中心点。创建了一些图像来说明所需的解决方案。

有没有解决这个问题的JS库，也许是d3？感觉上像是一个装箱问题，但也许在顺序和重力方面增加了一些复杂性。对画布解决方案不感兴趣。

如果容器足够宽

太紧，堆叠一些元素

更紧密地堆叠所有

我有一组不同大小的正方形和矩形,我想用PHP将它们组合成一个大的正方形/矩形.正方形通常是我想制作蒙太奇的图像 - 但有时它们只是数学对象.

是否有任何PHP算法,这种类型的东西叫什么？

更新:经过更多搜索后,我认为我想要的是bin包装问题.但是,我还想为某些类型的包装问题(如图像)添加一定量的随机化,以引起人们的兴趣.

我有一个概念性的问题,我有几个包,每个包里面都包含许多元素.元素是类型A或类型B.我希望在有限数量的箱中分发包,使得箱之间的分布A和B箱之间的差异不大.

这个问题非常复杂,因此我将尝试用严格的约束和一个概念性的例子来解释它.

约束

A package can only be used once
A package must be used entirely
The bins should have relatively equal distributions between `A` and `B` (max 5% deviation from the original ratio)
A package can be spread across all the bins in the given batch
I want to end up with as little as batches (size <= 3 bins) as possible

示例(概念)

Plate 1: 92 * `A`
Plate 2: 92 …

我正在寻找帮助改进放置奇怪形状块的算法.我的问题领域是奇怪的,但我的块的最佳类比是俄罗斯方块,除了它们可以有超过四件.块仍然只是由直角组成,但它们可以很长而且缠绕,它们可以分支等.

我试图在最小的空间内安排多个大型任意形状的块(我知道,bin-packing问题),但我目前的解决方案看起来很难看.我基本上放置一个,然后通过试图将它们放置在我的网格的原点然后慢慢地将它们推向不同的方向,直到它们不再发生碰撞来强制其余部分.它并不慢,但它没有任何尝试很好地适应它们,所以它们不会浪费整体空间.

我唯一能想到的就是按尺寸排序块,先放置最大的块,然后将最小的块放入最后的剩余孔中.但肯定有些方法会适得其反.

是否有任何启发式或近似算法可以帮助我？

结果将如下所示:

此外,也许我的gravatar放弃了这是Mega Man相关的......

我正在寻找任何3d bin打包算法的确定性实现,即在一个或多个较大的算法中包装许多小的和不同的长方体.解决方案可能与最佳解决方案不同.

它应该用C,C++,Java,C#,IronPython,IronRuby或任何其他可以从.Net代码中存储的语言编写.

我发现这个C算法http://www.diku.dk/hjemmesider/ansatte/pisinger/3dbpp.c,但它不会旋转长方体以找到最合适的.我没有将它们颠倒旋转,但应该可以进行水平旋转.

我想知道是否有人知道任何适合将N个未知大小的矩形装配到最小可能包含矩形中的算法.

最佳,我的意思是减少生成的包含矩形中剩余的空白量.

我想用它来从一系列图像中生成css sprites.

非常感谢,

伊恩

我正在研究俄罗斯方块式的HTML5游戏,需要加强空间优化算法.需要以最节省空间的方式将不同大小的矩形块添加到画布中.我知道这个块占用了多少空间,我需要找到一个最近的点,块可以添加一个固定的x坐标 - 绝对最近的点是一个不错的选择.

我实现了进行搜寻逐像素值向下推动,直到它找到形状足够的自由空间,在画布上检查版本,然后将其添加.此作品(慢)只有在空间罢了左右的算法可以放心地假设,如果第一像素列是安全的,然后可以加入整个块.

我需要让这个更加强大,这就是我认为应该去的地方.

存储四叉树来表示电路板状态使我能够更快地识别出有空间的位置.

为每个深度级别存储4个节点 - 每个节点为0表示完全为空,或者1表示"在某处有某些东西".每个渐进的深度级别都会提供有关电路板的越来越多的信息.

given(boardstate, block width, block height)
-calculate the largest grid space the block must span
  // a block which is 242x38 MUST span a 16x16 free space 
  // (based on 1/2 of smallest dimension)
-the block width requires n consecutive free spaces
  // (242/16) = 15
-find the first available 15x1 spaces in the board
-check the surrounding tiles at the next level of depth for collisions
  -check the surrounding tiles at …