标签: bin-packing

我正在寻找开源(最好是c ++)算法,用于矩形和/或不规则形状的2d bin包装.我找到了几篇关于这个主题的论文但没有代码.

我花了一些时间研究二维装箱算法。我在算法方面没有丰富的经验，尤其是在高级数学方面，但我可以编码:)

这里展示了我需要实现的完美示例：http://www.cutlistoptimizer.com。它有效，但我不知道它使用什么算法。

我尝试了很多方法，其中一些非常简单，例如https://codeincomplete.com/posts/bin-packing/ DEMO 这里，但它不支持旋转，这是必不可少的。

对我来说最有前途的是https://ssbothwell.github.io/greedypacker-react/ 不确定我做错了什么，但它并没有计算出最适合我的。我尝试了不同算法的不同组合。

演示数据：纸张尺寸：宽：2655，高：2100

{ w: 900, h: 320 },
 { w: 320, h: 900 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 386, h: 310},
 { w: 386, h: 310},
 { w: 386, …

正如标题所说,我需要C/C++源代码或一个库,我可以使用它来解决二维矩形形状的Bin Packing问题,其中bin也是矩形,矩形也旋转了90°角以更好地适应.我已经拥有了所有必需的值,所以我不需要在线打包算法.

我只找到一个lib来处理一个方形箱而没有旋转,这对我的需求来说不够高效.

我真的很感激任何处理矩形bin和旋转的C/C++.

谢谢.

PS:计算所需的时间并不重要,只有结果.

PPS:它必须是C或C++,我没有找到任何有用的搜索stackoverflow ...

我有一个优化问题.这是一个包含20个部分的产品(生产顺序无关紧要).我有3台类似的机器可以生产所有20个零件.

我用分钟表示了20个部分(即生产第一部分需要3分钟,生产第二部分需要75分钟等)

ItemTime<-c(3,75,55,12,45,55,11,8,21,16,65,28,84,3,58,46,5,84,8,48)

因此生产1种产品需要730分钟.

sum(ItemTime)

目的是通过将好的物品分配给三台机器来最小化一种产品的生产.

sum(ItemTime/3)

所以实际上我需要尽可能接近243.333分钟(730/3)

可能性的数量巨大3 ^ 20

我想有许多不同的最佳解决方案.我希望R给我所有这些.我不需要知道需要机器1 2和3的总时间:我还需要知道给机器1,机器2和机器3提供哪些物品.

或者,如果它太长,我想选择一个尽可能合理的样本而不重复......

我可以用R语言解决我的问题吗？

我知道我的问题可能没有“完美”的解决方案（这听起来像是背包或垃圾箱包装问题的变体），但这是我的情况：

我想将 SQL 数据库表列表分成 n 个（假设为 7 个）大小大致相同的堆（这样我可以在整个星期内大致平均地分配一些维护任务）。

假设我有 100 个表（这可能更高或更低，但不太可能高于 5000），范围从 1 到 10,000,000（当然，更大的表不太常见）。

我最初的想法是按字母顺序（伪随机）对表格进行排序，然后从头开始遍历，当总数超过 Sum(Size)/7 时移动到下一组。对于某些数据库，这可能会正常工作，但如果两个巨大的表彼此相邻，则这会导致非常不平等的组。（这并不像听起来那么不可能，考虑两个巨大的表，Account_History 和 Account_History_Archive）。

是否有任何普遍接受的技术可以为各种源数据提供“良好”的结果？我倾向于更简单的技术，而不是更精确的分组（如果某些日子的维护时间比其他日子稍长，那没什么大不了的）。

给定n 个无限容量的箱子，我想将m个物品装入其中（每个物品都有特定的重量），同时最小化最重箱子的重量。

这不是传统的垃圾箱包装/背包问题，其中垃圾箱的容量有限，并且您试图最大限度地减少垃圾箱的使用量；我有一定数量的垃圾箱，并且想将它们全部使用，以使最重的垃圾箱的重量尽可能低。

这个问题有名字吗？我查阅了很多带有关键词的论文，但没有发现类似的内容。

干杯。

我正在寻找一种算法，可以帮助在较大的矩形内分布不同大小的矩形，同时最大限度地减少重叠。

我看过装箱算法，但它们似乎最小化了矩形之间的空间量（在我的情况下，所有被包装的物品都是正方形）。

我想我想最大化所有正方形和外部矩形边界之间的距离。

这是我正在尝试做的一个例子：

我尝试对从我的电子商务网站运输产品进行优化。

我不使用插件进行电子商务，仅使用asp.net mvc 5。

我向FeDex API询问购物车中所有物品的运费。因此，如果用户在购物车中有3件商品，它将像3件包裹一样进行计算。我需要一种方法来计算包装的尺寸，如果超出尺寸，则将其分成更多包装。

我在c ++和php（Here and Here）中找到了示例，但是我不知道这些语言...

如果您可以帮助我找到c＃示例或帮助我将此php转换为c＃，以便我可以了解它们的工作原理，则...

坦克！

编辑：

我完全找到了我需要的东西，但是它在c中……我需要为其创建一个dll，然后在我的应用程序中使用它 https://github.com/wknechtel/3d-bin-pack

问题如下:

您有n个行程长度(以km为单位),应在m天之间进行划分,以使每天最大长度总和最小化.例如,在3天内划分的行程长度[1,5,2,6,8,3,2]导致[1,5,2] [6] [8,3,2]因为最大日长度总和是我们能达到的最低点.

是否有一种描述处理这种问题的算法？我遇到了bin包装和背包问题,但没有一个能解决我的问题.我可以想象它可能是对bin包装的一点修改但是没有得出结论.

我正在尝试使用基于极值点的方法来实现 3D 打包算法。介绍这种方法的论文可以在这里看到：Extreme Point-Based Heuristics for 3D Dimensional Bin Packing

论文最后还有一个伪代码算法（Algorithm 1 Update3DEPL）。我很难理解作者的意思如下：

• 他用标识符指的是什么Yx, Yz, Xy, Xz, Zx, Zy？我知道他用它来索引数组，但是我不知道他的意思。我很确定作者每次都想引用一对轴，但我又不知道这意味着什么。

• 我更困惑的是该函数的CanTakeProjection作用以及它需要上述符号（Yx，Yz，...）的用途？该功能的解释也没有帮助我：

CanTakeProjection：如果 EP k 位于项目 k 的一侧，则函数返回 true

极端点 k 应该如何不位于项目 k 的一侧？或者这是一个错字，它应该如下所示：

CanTakeProjection：如果 EP k 位于项目i的一侧，则函数返回 true