问题标签 [bin-packing]

我将这个2D bin-packing 算法从 JavaScript移植到 PHP，并使用它在 sprite map 中布置一些图像。

它适用于规则形状的图像（例如，所有正方形），但对于更大、更复杂的数据集，它会产生略微损坏的结果。

您可以看到 16 是一个细长的图像，而 118 紧贴在其下方。然后 57 有点高，但随后 121 和 126 与 118 对齐/略低于 16，与 57 重叠。不知道为什么要这样做。

有人知道我可能会出错吗？

更新：注意到几个地方的代码应该永远无法命中并抛出异常；意识到findNode总是会找到新创建的节点，搜索我们已有的节点是没有意义的。清理了一点，但它仍然表现出完全相同的行为。开始认为这个算法是行不通的。

免责声明：这是学校作业

大家好。我已经在这个 Bin Packing 程序上苦苦挣扎了两周，我还有最后一个障碍要克服：我的二叉搜索树的查找功能给了我不正确的结果。

二进制搜索树.cpp

二叉树节点.h

BinPacking.cpp

用户输入到 main（未显示）

预期产出

电流输出

我知道我即将完成这项任务。我知道问题是什么，但我无法解决它。拜托，你会帮助我吗？

对于一个作业，我得到了装箱问题，并要求我展示如何从优化版本中解决问题的决策版本，反之亦然。我知道要解决决策版本，您只需将优化版本中使用的 bin 数量与指定的最大 bin 数量进行比较，但我如何使用决策版本来解决优化版本？

假设你有 k 块石头和 m 块石头类型你有 f1 块石头来自第一种类型，f2 来自第二种类型，依此类推。

（即总和（f_i）= k）。

此外，我们得到一个正整数 r。

最少需要多少个桶，这样我们才能将石头类型分配到每个桶的大小不超过 r 的桶中？（我们也知道对于每个 i，f_i <= r）。

这个问题实际上是某种装箱问题，所以我不确定它是否有确切的答案，但我们可以给它一个上限吗？

一个微不足道的上限的例子是 m，因为这将允许我们将每种石头类型打包在他自己的桶中。

一个不起作用的界限的例子是 k/r。原因是如果k=9，r=3，我们有5种石头，f1=2，f2=2，f3=2，f4=2，f5=1，

那么无论我们如何划分石头类型，都必须有一个大小> = 4的桶。

同一类型的所有石头都必须放在同一个桶中。

有什么建议么 ：） ？

编辑：m 和 f_i 是未知的，我正在寻找一个界限，它使我能够为所有 (m,f_i's) 组合分配石头。

另一个例子：假设 r = 3。我将证明 k/2 个桶就足够了：

让我们用 x 表示有 3 块石头的类型数量。y 将表示恰好有 2 颗宝石的类型数量，z 将表示单颗宝石类型的数量。

根据定义：3x + 2y + z = k。我们可以为 3 块石头类型分配 x 个桶。

如果 (y > z) {第一种情况}：将其中一个 y 类型与其中一个 z 类型一起放入一个桶中{我们有 z 个这样的桶}。

将其余的 y 类型放在一个桶中。

由于 y > z 我们使用了 x+y 桶，并且由于 3x + 2y + z = k => x+y <= k/2。

if (z >= y) {第二种情况}：很容易看出我们可以把所有的石头都装在 k/3 个桶中（每个桶都可以装满，正好包含 3 块石头）。

此外，对于 r=3，这将其绑定得很紧（如果 x=z=0 和 y=k/2，那么我们正好需要 k/2 个桶）。

现在的问题是：k/2 个桶是否适用于所有 r 值？

我可以证明 2k/(r+1) 个桶的下限（即紧实例），但它与 k/2 相差甚远。任何人都可以收紧界限吗？

我正在尝试使用最大矩形算法来实现 2D 装箱，如下面的论文中所述。

http://clb.demon.fi/files/RectangleBinPack.pdf

为了实现这一点，哪种类型的数据结构最合适？谷歌搜索后，我发现使用树的 Guillotine 打包算法有不同的实现。是否也可以将相同的方法应用于此。算法本身对我来说不是很清楚。我也可以对此进行更多澄清吗？

这是在 python 中实现的（更多测试）

我对使用Packery.js jQuery 插件进行基于 js/DOM 的 bin 打包的上图中的结果（在 python 中实现）感兴趣。Packery 被构建为从左到右，从上到下工作，但我想知道是否使用圆形边界框而不是视口作为其边界可以做到这一点。

最终，我想用它来呈现许多具有各种尺寸和比例的图像缩略图。

任何代码示例或其他指针将不胜感激。

我有很多这样的名字：

我想将列表中的名称提取为字符串，每个名称用管道字符 (|) 分隔。每个新字符串应小于 48 个字符，例如输出应如下所示（但小于或等于 48 个字符）：

我希望新字符串的数量尽可能少，可能不维护数组中字符串的顺序 - 但我不知道如何在 javascript 中执行此操作。

我知道我可以做一些事情，比如遍历名单并将下一个名称添加到临时字符串中。检查此临时字符串的长度，如果超过 48 个字符则输出。继续循环，直到我们用完名称，但这似乎不是很有效。例如，如果一个短名称后跟一个非常长的名称，那么字符（可以在临时字符串中由另一个较小的名称填充）将被浪费。

关于如何最好地实现这一目标的任何指示？

我试图弄清楚在给定这些约束的情况下是否可以简化常规的 2D 打包问题。对于 3 到 12 之间的 s，您有 n 个规则的 s 边多边形。它们都具有相同的边长。我们需要最小化边界正方形的面积。

我认为让所有具有相同边长的常规包装可以更容易，因为某些配置将始终完美地贴合在一起。虽然我不确定这个属性是否有用，因为局部最小值可能不会转化为全局最小值。

我一直在寻找一个明显比我最初想象的更不寻常的问题的解决方案。Optaplanner 看起来很有前途，但相对缺乏 Java 经验，我想在深入研究之前调查这是否完全不可能。

我正在尝试为 n 名员工安排任务。这里的主要区别在于，目的是让所有员工在任何特定时间都保持忙碌。完成任务所需的时间在很大程度上是次要的。这形成了具有以下变体的装箱/作业车间问题：

• 一维
• 任务之间的“相互关系”。例如，一项任务在开始之前可能依赖于另一项完成，而该任务可能归属于不同的工作人员
• 每个任务只能归于某些人
• 在任何给定时间跨箱的最小值将被最大化

据此，我认为任务所需的输入将是“最早开始时间”、“最晚完成时间”、“持续时间”、“与其他任务的链接”、“合适的工作人员”。然后任务应该落入每个员工的垃圾箱 - 就像俄罗斯方块一样！

这显然是我阅读的调度示例的一个转折点。你认为这是可以实现的吗？您是否会推荐任何预先存在的示例（手册中没有一个完全匹配）？

任何朝着正确方向的轻推将不胜感激 - 为这个问题的新手性质道歉。

我正在尝试进行 First-Fit bin 包装。这是我编写的代码，每行都有注释作为注释：

基本上，该getNumber(i)部分是一个返回数字的函数。我正在使用循环将实际数字（其中 6 个，更具体地说）添加到称为“数字”的 ArrayList 中。

我已经尝试在每个阶段打印出数字并查看它正在处理的数字 - 但它似乎只是无缘无故地随机跳过了一些数字。例如，对于1,2,3,4,5,6它添加到的第一个数字的 ArrayList 输入bin[0]是3（应该是1），然后它还添加6到bin[0]并忽略所有其他数字并进入下一个 bin 数组。

谁能发现我做错了什么？

谢谢