问题标签 [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 投票
0 回答
182 浏览

java - bin packing boolean 如果 bin 已满

我正在尝试使用 Next Fit 在线实现装箱算法。所以我事先不知道盒子的大小。无论如何,我有一个具有高度和宽度的 Box 类。一个列类,它表示和堆栈的盒子和一个卡车类,它保存着一堆盒子和一个布尔值,如果卡车是满的。

然而,当我在我的测试课上时,我会生成一个盒子列表和一个卡车列表来存放这些盒子。我将盒子添加到每辆卡车,当卡车几乎没有空间时,最后一个盒子尝试添加,但它不适合,所以布尔值 isFull 设置为 true,但进入该方法的盒子是然后迷路了。如何将盒子添加到卡车上,如果它已满,在下一辆卡车的呼叫中使用同一个盒子?

非常感谢

代码

0 投票
1 回答
584 浏览

algorithm - 关于优化和决策版本的装箱

我正在准备考试,我们得到了一组练习题。这是我正在努力解决的问题,我希望有人可以帮助阐明解决此问题的正确方法: 在此处输入图像描述

这是我最初解决这个问题的方法:

决策版本:要使用决策版本找到最佳解决方案,我会尝试使用各种 K,直到得到肯定的答案。假设优化的解决方案是 7,我会尝试:

所以现在我们知道最佳解决方案是 7 个 bin,我们通过按大小从最大到最小对项目进行排序来解决决策版本,然后将填充最大到最小的 bin 填满,然后循环遍历这些 bin,直到它们不再存在集合中的元素。

如果我们有一个最优解决方案并且我们想要解决决策版本,我将获取最优解决方案返回的箱数,并在决策版本上运行它,看看它是否返回是。

我以前从未真正见过这样的问题,所以我不确定正确的格式应该是怎样的。

任何帮助将不胜感激!

0 投票
1 回答
928 浏览

java - 二维装箱Java?

我需要使用 Java 中的在线最佳拟合解决 2d 装箱问题。我不知道我应该如何找到放置下一个盒子的正确位置。

我刚在想。我应该将每个 2d bin 的所有顶盒位置存储在某个地方吗?我是否应该在每个 bin 中保留一个数组和一个 2d 数组之类的东西,它们在数组中有多空以及每个顶盒在 2d 数组中的位置?

0 投票
1 回答
322 浏览

algorithm - “松散”装箱算法

想不起来怎么称呼这个,所以我的谷歌搜索也很短......

我正在做一些类似于基本的垃圾箱包装问题的事情,但有一些改变让我感到困惑。

  1. bin 的数量始终为 3,并且所有 3 始终是相同的尺寸(等于所有项目尺寸总和的 1/3)
  2. 每件物品都必须放在垃圾箱中
  3. 如果项目不能完全放入一个容器中,则它们可以被“分割”成多个连续的容器。最小化这个

有了这三个标准(尤其是第 3 个),我不确定问题是否是 NP 难题了,但是第四个标准使我称之为“松散”问题。

  1. 垃圾箱大小不必严格执行。如果一个项目要被“过度填充”到一个垃圾箱中,比如说,垃圾箱大小的 10%,那很好,但前提是它可以容纳整个项目(不要为零散的项目过度填充)。

这仍然是一个结构化的问题,还是我把我的标准搞砸了,以至于它几乎无法解决了?

如果你很好奇,我正在使用它来呈现包含许多(或少数)链接的许多(或少数)类别(项目)的 3 列(箱)。

目标语言是 PHP,但目前最好使用伪代码。

0 投票
1 回答
223 浏览

algorithm - 空间利用算法或网格创建算法

嘿,我们正面临空间利用问题,或者我不清楚我应该给问题起什么名字。

基本上它是一个网格问题。

我试图用一张图片来解释我的问题。

在此处输入图像描述

问题陈述有点像下面。

  1. 带有对角线的盒子是一个必须以最佳比例分布的物品,例如它应该适合所有可用的容器。
  2. 容器以不同的颜色显示。
  3. 现在所有容器都将呈矩形。
  4. 所有容器必须以纵向模式或横向模式放置。

容器和项目都可以测量宽度和高度,对于程序它们基本上是像素。

根据其他成员的评论,SpektreLasse V. Karlsen 这里是对相同的澄清

  1. 这是一个二维排列
  2. 是的,我们可以重新排列容器以实现最佳模式。
  3. 项目的任何部分都不应在空白处。项目必须是任何容器的一部分。
  4. 项目可以与容器重叠,并且高度和宽度可以因容器而异。并且项目的高度宽度也可以变化,但形状将始终保持矩形。
  5. 如果项目的位置固定在左上角,则它是更可取的。
  6. 是的,它有点像 bin 打包算法,但该算法的唯一问题是,在 Bin 中打包项目更多,容器是一个,在我们的例子中,项目是一个,容器更多。所以基本上它是一个分布问题。
  7. 想法实际上是我们有容器的大小并且需要放置容器以便我们可以创建那个矩形的问题。

该程序应给出以下输出

  1. 容器的位置
  2. 容器内部的部分物品。
  3. 和排列图案。
0 投票
1 回答
126 浏览

algorithm - 如何在矩形容器内分配不同宽度和高度的矩形列表,最大化项目之间的距离?

我需要一个接受两个输入的函数:

  • 具有宽度和高度的边界框
  • 具有不同宽度和高度的矩形项目数组(都小于边界框)

它将输出具有附加position属性的相同项目的数组(可以改变原始项目),x并且y使项目之间的距离最大化(注意 - 不是点之间的距离,需要考虑项目的尺寸)。

它不一定是经过数学证明的最佳解决方案,足够好的启发式方法是可以的

我看过装箱,但它似乎与我想要的相反。

任何语言都是可以接受的,甚至是伪代码。

我不知道从哪里开始。现在我只是随机化位置,偶尔会出现重叠的项目,这是不可取的。

0 投票
1 回答
813 浏览

c# - Gurobi C# 优化盒子包装

我有三个产品和五个盒子:

尺寸为:

我想选择所有产品都可以装入的最小体积的盒子。

我编写了以下代码,并且我知道我应该添加约束以仅在其中选择 1 个框。但它在当前状态下不起作用(给出不可行的 sol)。代码如下:

在此先感谢您的帮助,

注意:我给出了简单的问题 (1D) ,实际上我真正的问题是 3D 问题。在这种情况下,我只考虑产品和盒子的长度,但实际上我还应该考虑宽度和高度。

0 投票
0 回答
578 浏览

3d - 使用 optaplanner 进行带有盒子旋转的 3D 装箱?

我正在评估http://www.optaplanner.org/以解决 3D 装箱任务。我不清楚什么 - 如何配置记分器/求解器和框以接受 X、Y、Z 轴的旋转?

0 投票
2 回答
430 浏览

matlab - 如何确定边界切割利用率 MATLAB?

处理二维矩形嵌套。需要找到材料的利用率百分比。假设我有每个矩形的长度、宽度、左下位置。确定边界切割利用率的最佳方法是什么?

目标:- 找到红线下的区域。

附上的示例图像描述了我做了什么以及我需要什么。

我做了什么 在此处输入图像描述

我需要的 在此处输入图像描述

另一个填充有余量的矩形示例图像 在此处输入图像描述

0 投票
5 回答
1758 浏览

r - 在R中创建相等和的组

我正在尝试将我的 data.frame/data.table 的一列分成三组,总和相等。

数据首先从最小到最大排序,这样第一组将由大量具有小值的行组成,而第三组将由少量具有大值的行组成。这是通过以下方式在精神上实现的:

虽然成功,但我觉得必须有更好的方法(也许我缺少一个非常明显的解决方案)。

  • 当矢量化方法可用时,我从不喜欢使用循环,尤其是嵌套 ifs - 即使有 100,000 多条记录,此代码也会变得非常慢
  • 这种方法将变得不可能复杂到编码到更多的组(不一定是循环,而是 ifs)
  • 需要预先订购色谱柱。可能无法绕过这个。

作为细微差别(不是说它有区别),但要求和的数据并不总是(或永远)是连续的整数。