问题标签 [bin-packing]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
697 浏览

javascript - 与 masonry.js 或 isotope.js 类似的 bin-packaging 布局,无需按现有元素排序

我试图创建将填充元素的布局,以最小化它们之间的空白。问题是我尝试过的所有库都按照定义的方式从左到右和从上到下对项目进行排序。下面是一些例子:

这些项目将从左到右和从上到下填充 layout_wrapper,从 1 开始并以 4 结束。但是这样可能会有必须用其他合适的项目填充的间隙 - 比如说 1、4、3、2 - 将是填充布局的最佳方式。

但我无法完成这项工作。我知道这对于动态内容加载等情况来说是少数,当内容必须以它的方式放置时,但在我的情况下,我需要其他行为。

那么,有没有人知道如何在 masonry.js 或任何其他类似的库中使 bin 打包算法以我需要的方式工作?谢谢。

0 投票
1 回答
190 浏览

arrays - 动态对象布局

我有一个由 50 个对象组成的数组,每个对象的宽度和高度都不同。我的目标是创建面板来容纳这些对象并使它们保持有序,但是这个面板不能超过 300 像素的宽度或 600 像素的高度,所以我必须在这个面板中尽可能多地放置对象,如果它们不适合然后我需要创建一个新面板,直到没有更多项目要附加。
因此,例如,如果我有一个尺寸为 150x75 的项目,那么我只能放置另一个相同尺寸的对象,如果下一个项目没有这个尺寸,那么我创建一个空对象来占用这些空白空间。可以在Codepen.io上找到一个示例 现在只要每个项目的高度为 75px 就可以工作,但是当高度超过这个值时就会出现问题。几天来,我一直在尝试解决这个问题,但是这个特殊的任务似乎会抛出整个设计。这是我检查物品是否合适的逻辑:

逻辑有什么问题吗?如果我重新排序这些物品,我现在可以解决它,但它们必须保持有序。完整代码可以在Codepen.io上找到

0 投票
1 回答
757 浏览

algorithm - 一维装箱问题的 MBS 算法(最小 bin slack)

我正在努力解决一维装箱问题,作为初始种群,我将从 MBS 的生成器粒子开始。我在网上寻找 MBS (最小 bin slack)算法,但找不到。请问有人可以帮我吗?

0 投票
1 回答
1180 浏览

javascript - 二维装箱的变化?

根据我对垃圾箱包装的理解,您正在尝试将预定且通常不同尺寸的物体装入一个或多个容器或预定固定尺寸的“垃圾箱”中。我有一个问题,我有一个固定大小的容器和必须适合它的固定数量的元素。不同之处在于我的元素不是固定大小,但可以调整为特定大小的任意倍数数字。例如:

假设我有 3 个对象或元素,它们必须完全适合 280x420 的容器,并且对象的大小必须重新调整为 140 的倍数。

因此,它可以像这样适合:(或垂直翻转)

或:(或水平翻转)

最终,每个盒子的大小将根据统计动态确定。(例如,如果一个项目有 90% 的统计数据,而另外两个有 2% 和 8% 的统计数据,那么显然 90% 会得到更大的盒子。)但是,我尽量不要过于复杂还没有,所以只是创建一个算法来填充容器是我现在的主要目标。

我一直在研究不同的算法,但还没有想出一个理想的方法来尝试这个。任何指针?例子?现有的数学或其他类似的算法?


一个更复杂的例子是:6 个项目,560x420 的容器。元素 JSON: { "0": "432", "1": "389", "2": "403", "3": "190", "4": "215", "5": "832" } 一种可能的呈现方式:

0 投票
3 回答
1354 浏览

c++ - 包装矩形而不旋转?

包装矩形的算法是没有旋转的吗?

也许在 C++ 中实现?

我发现了这个

  • 断头台BinPack
  • 货架箱包
  • SkylineBinPack

但他们旋转矩形。

0 投票
1 回答
304 浏览

algorithm - 寻找多种装箱解决方案

我有 3 个大小可变的盒子:

我有尺码的物品a: 1, b: 2, c: 2, d: 3, e: 5

我显然可以将它们放在以下模式中:

但你也可以这样做:

有没有办法让我得到所有可能的包装?

这感觉像是一个装箱挑战,但我并不是试图找到一个“最佳”解决方案,而是所有(或至少多个)可能的解决方案。

我想我可能会以随机顺序对项目运行一个天真的装箱算法,直到找到解决方案,但这似乎真的效率低下......

有任何想法吗?

0 投票
1 回答
990 浏览

c++ - 装箱算法 - 实际变化

我正在尝试解决一个奇怪的垃圾箱包装问题。原始问题的链接在这里 (对不起,很长的问题,感谢您的耐心等待)

我正在重复以下问题:我正在尝试编写一个为分隔面板生成绘图的应用程序。

我有 N 个隔间(2D 矩形)(N <= 40)。每个隔间都有一个相关的最小高度 (minHeight[i]) 和最小宽度 (minWidth[i])。面板本身也有一个 MAXIMUM_HEIGHT 约束。

这 N 个隔间必须在一个列式网格中一个在另一个之上堆叠,以便每个隔间都满足上述约束。

此外,每列的宽度由该列中每个隔间的 minWidths 的最大值决定。

此外,每列的高度应该相同。这决定了面板的高度

我们可以在任何列的剩余空间中添加备用隔间,或者我们可以将任何隔间的高度/宽度增加到指定的最小值之外。但是,我们不能旋转任何隔间。

面板的 MAXIMUM_HEIGHT = 2100mm, minwidth range (350mm to 800mm), minheight range (225mm to 2100mm)

根据选择的答案,我制定了整数线性规划。但是,考虑到问题的组合性质,求解器似乎“挂”在 N > 20 上。

我现在正在尝试实施一个变通解决方案。

隔间按 minWidths 的降序排列。如果 minWidths 相等,则按 minHeights 的降序对它们进行排序。然后我使用First Fit 递减启发式
来解决它。这给了我总面板宽度的上限,以及当前列宽的列表。

现在我尝试使面板宽度更小,并尝试将我的馈线安装在那个更小尺寸的面板中。(我能够以有效的方式检查馈线是否适合给定的列宽列表)

面板宽度可以通过以下方式缩小:
1. 取任意一列,将其替换为下一个较低 minWidth 进纸器的一列。如果该列已经是最低的 minWidth,则尝试将其删除并检查。
2. 取任意一列,将其替换为具有更高 minWidth 进纸器的列,然后移除另一列。
3.还有什么办法,不知道有没有人指出会很高兴。

我已经正确实施了第一种方式。以下是代码。但是,我无法正确地将其他方式放入代码中。

任何帮助将不胜感激。

谢谢

0 投票
1 回答
1079 浏览

python - 如何使用 OpenOpt 解决 3D 多装箱问题

我正在学习优化,而且我是 OpenOpt 的新手。

我想表示每个进程都有 3 个资源使用指标(CPU、内存和网络)的进程,并且我想根据以下限制将 N 个进程分配给组/箱:

理想情况下,我希望有这种类型的输出:

问题:我该怎么做?如果使用 OpenOpt 无法做到这一点,是否有任何其他库可以帮助我解决这个问题?

这是我的初始代码: https ://github.com/vonpupp/mdbp/blob/master/ksp_2.py

非常感谢!

0 投票
0 回答
154 浏览

algorithm - 安排病人的算法;更简单的装箱版本

我目前正在开发一个调度工具,我有多个位置(箱),每个位置(箱)都有不同的座位容量,我需要放置病人。患者要么是阳性,要么是阴性。我不能在同一个位置混合阳性和阴性患者。

由于每个要求让患者就座,我需要能够说明我们是否可以根据患者是积极还是消极来让他们就座。

不需要将患者分配到一个位置,因此患者的安排可以是灵活的,我只需要最大限度地提高容量。

在进行计算时,我会知道:

  1. 有多少个位置。
  2. 每个位置的座位数。
  3. 已获得席位的阳性患者人数。
  4. 已获得席位的阴性患者人数。

我相信有人会对此有明确的解决方案,但目前我看不到树木的树木。

0 投票
0 回答
76 浏览

c# - 给定一组随机的盒子和一组空间,你如何找到最佳组合?

我有一个有趣的任务,我不知道从哪里开始。

想象一下,您有一组空间(大小都相同)和一组框(可变整数大小,1 或 2 或 3 个体积单位)。每个空间可以容纳 4 个单位的体积。给定一组随机的盒子,什么样的组合会留下最开放的空间(即最密集的包装)。

我不希望任何人为我编写我的代码,但我真的可以使用一些建议来解决这样的问题从哪里开始。任何人都可以帮忙吗?

我尝试列出所有排列,然后选择具有最多“开放空间”的排列,但它在计算上非常昂贵。如果这有所作为,我正在使用 C#。

代码有点冗长所以这里是伪代码