问题标签 [bin-packing]

如何概括 3D 单箱包装算法以找到可以包含项目集的最小箱尺寸？

我正在研究分支定界算法，是否有条件让我切分支而不是当前的最佳解决方案？

我希望足够清楚，并感谢任何帮助！

我尝试从我的电子商务网站实现运输产品的优化。

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

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

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

如果你能帮我找到 c# 示例或帮我将这个 php 转换为 c#，这样我就可以理解它们是如何工作的......

坦克！

编辑：

我已经找到了我需要的东西，但它在 c 中......我需要为它制作一个 dll，然后在我的应用程序上使用它 https://github.com/wknechtel/3d-bin-pack

我正在寻找一种可以执行以下操作的算法（希望是 .net 实现）：我有以下数据：

1. 一份技术人员名单，每个人都有不同的技能（可能不止一个）。
2. 服务时间窗口（例如 8-12）
3. 此时间窗口内所有先前安排的工作的列表（每个都有它所需的技能）

给定一份新工作（具有所需技能），我应该检查新工作是否并分配给任何可用的技术人员（只要他们的技能支持，以前的工作可以在技术人员之间转移）。也不能超过服务时间窗口，因此不能将 1 小时的工作安排在 11:30

最初我考虑做装箱 FFD 变体是我预装了箱子（技术人员），在寻找一个箱子来放置工作时，我也会检查技能匹配。作业列表将包含所有以前的作业和新的作业（按大小降序排序），并且代码停止，因为作业无法放置在任何 bin 中，或者它在所有作业都安排好后完成。

理论上它可以工作，但后来我想到了以下场景：

• 技术员：T1（具有技能 S1 和 S2）、T2（具有技能 S2 和 S3）
• 以前的工作：J1（需要技能 S2），整个时间窗口的持续时间。
• 新工作 J2（需要技能 S1）

可能会发生这样一种情况，即 J1 被分配给 T1，然后 J2 无处安放。

所以我考虑在工作列表中添加第二个排序：工作将按大小降序排序，然后按实际可以执行它们的资源数量升序排序。这将使 J2 排在第一位，因为可以做到这一点的技术人员较少。

是否有解决此问题的特定算法或者我的方法是否足够好？

谢谢

我正在研究一种装箱问题，但并不完全相同。该问题要求将n件物品放入最少数量的箱子中，但总重量不会超过箱子的容量。（经典定义）

不同之处在于：每个项目都有一个权重和bound ，并且 bin 的容量由该 bin 中项目的最小边界动态确定。

例如，我有四个项目 A[11,12], B[1,10], C[3,4], D[20,22] ( [weight,bound] )。现在，如果我将物品 A 放入一个 bin 中，称它为 b1，那么 b1 的容量变为 12。现在我尝试将物品 B 放入 b1，但失败了，因为总重量为 11+1 =12，容量为b1 变为 10，小于总权重。因此，B 被放入 bin b2，其容量变为 10。现在，将项目 C 放入 b2，因为总重量为 1+3 =4，而 b2 的容量变为 4。

我不知道这个问题是否已经在某些地区以某种名称解决了。或者它是在某处讨论过的装箱变体。我不知道这是否是发布问题的正确位置，感谢任何帮助！

我想知道如何解决“具有相对成本的一维装箱问题”。我们将 N 个卷（具有给定大小）打包到 M 个箱（具有给定容量）中，并具有每个箱的每个卷的成本矩阵 (NxM)。因此，总成本应该最小化。

你能建议任何算法来解决这个问题吗？或者，可能有任何开源库可以做到这一点？

谢谢！

我有一个令人头疼的问题，感觉类似于经典的垃圾箱包装问题，但我无法确定。任何帮助表示赞赏...

问题：

我有一组尺寸相同的产品，但有不同颜色的变体和不同的订单数量。

我可以以任何组合包装它们，但我只能拥有规定数量的不同内容的盒子。

我可以提供不同数量的每个盒子。最佳解决方案是超过请求数量的产品数量最少的解决方案。

示例：一个盒子可以装 4 件产品，我可以使用 2 种不同内容的盒子，我需要运送 100 * 红色、200 * 蓝色、300 * 绿色、400 * 黄色；

我不能装 25 盒红色、50 盒蓝色、75 盒绿色和 100 盒黄色，因为我只允许盒子里有 2 个不同的独特内容，这将是 4 个。

因此最佳解决方案是：

100盒1*红2*蓝1*黄

150盒2*绿色和2*黄色

在这个例子中，我已经完全满足了我的所有数量，因此零浪费。

假设订单只需要 395 黄色；上述解决方案会浪费 5 个黄色，但没有浪费更少的解决方案。产品浪费最少的解决方案是最好的。

我有一组盒子对象，由它们的 (x,y,width,height) 属性定义，如下所示：

框 Q 锚定在角点 C。我如何以编程方式扩展框 Q 以占用它拥有的所有可用空间，同时保持其纵横比？

通过将框扩展为非常大（从右上角）然后对齐到最远框的顶部边缘（在本例中为 5），我有一些运气。如果此时其他框与 Q 重叠，我删除最远的框 (5) 并重复（对齐到 4 的顶部边缘），直到没有框重叠。这种方法的问题在于，一个框可能与 Q 重叠（下图中的框 2），但是当我缩放以满足其顶部边缘时，它不再被包含，如下所示：

任何关于方法的想法将不胜感激，

乔什

我有一个概念问题，我有几个包，每个包里面都包含许多元素。元素是 typeA或 type B。我想以这样一种方式将包分配在有限数量的箱中，以便箱之间的分布A和B箱之间的分布差异不大。

这个问题非常复杂，因此我将尝试用硬约束和概念示例来解释它。

约束

示例（概念）

这样的总分布是 302 *A和 191 *B总共产生 493 个样本，得到的比率是 61.25%A和 38.75%B

期望的结果：

一组最小化的批次，其中每个批次最多包含 3 个箱（长度 <= 92），假设每个箱的类型在 52 到 60 之间，类型A在 32 到 40 之间B（总和不超过 92）。

问题

建议使用什么算法或方法来解决这个问题，一个简单的建议方案就可以了（考虑到我到目前为止一直在尝试的东西（见下文）并没有走得太远）

迄今为止我的尝试背后的想法

这也是我被卡住的地方，目前这并没有尝试最小化垃圾箱的数量，也没有检查比率。此外，我有一个挥之不去的想法，即我尝试这样做的方式与解决此类问题的智能方式相去甚远。

我目前正在开发一个 Bin Packing 程序，需要知道以以下方式对盒子（任意宽度、长度和高度）进行排序的最有效方法是什么？

最大（类似立方体）形状的盒子然后是最高的（类似薄的）形状的盒子

至

最小的（类似立方体）形状的盒子然后是最短的（类似薄的）形状的盒子

我尝试过对体积然后高度、高度然后体积和表面积然后高度进行排序。它们是不错的方法，但我想要一个更优化的解决方案。

我想找到所有将n元素分配到b垃圾箱但没有“重复”和空垃圾箱的方法。

例子

如果我有n = 3元素和b = 2垃圾箱并从这个 stackoverflow 线程Bin 打包蛮力方法应用蛮力方法，我会得到以下结果：

“重复”的定义

一半的结果是重复的。仅切换 bin 的顺序：first 和 last 相同，2nd 和 2nd to last 相同，等等...

空箱的定义

我不希望任何垃圾箱是空的。如果你看前面的例子，第一行和最后一行有一个空的 bin。