问题标签 [bin-packing]

正如标题已经说的那样，我需要 C/C++ 源代码或库，我可以使用它来解决 2D 矩形形状的装箱问题，其中箱也是矩形的，并且矩形也被旋转 90° 角以更好地适应。我已经有了所有必需的值，所以我不需要在线打包算法。

我只找到了一个处理方形箱且没有旋转的库，这对于我的需求来说效率不够高。

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

谢谢。

PS：计算所需的时间并不重要，重要的是结果。

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

请让我知道哪种算法适合以下问题：

在给定的 3 个月期间，我们有有限数量的项目（通常 < 50 个）。每个项目都有几个小时。

在同一个 3 个月期间，我们有有限数量的资源（通常 < 100）。

每个资源每月可以消耗唯一数量的小时数（考虑假期、个人假期等 - 每月这个小时数已经为每个资源预先计算并且可用）。

可以将一种资源分配给多个项目。

我认为，如果我们将项目视为垃圾箱，将资源视为对象，将小时视为对象体积，这就像一个装箱问题。至少有两件事使它偏离了正式的装箱问题：

1. 资源是流动的物体，可以在一个容器中滴几个小时，在另一个容器中滴几个小时。
2. 最佳解决方案不是尽量减少使用的箱（项目）的数量，而是尽量减少资源在项目之间拆分的次数，并确保所有项目都被使用。

我觉得我可能正在用垃圾箱包装角度追逐鹅。有没有更适合这个的算法？

使用这个2d bin-packing algorithm (EDIT: Fixed demo) 这是一个变体，我怎样才能得到每个 bin 的最终 bin 宽度和高度？

我的演示代码如下：

原始算法只处理一个不断扩展的 bin，因此我对其进行了修改以获取最大宽度和高度。然后我遍历块数组，调用打包器，将合适的块推送到一个新数组，然后将它们从“块”中取消设置，直到“块”为空。这是否是最好的方法是另一个问题的主题。

无论如何，我已经尝试像这样修改growNode：

它适用于除第一张以外的每张纸。我也尝试用其他一些方法添加这些行，但没有成功。我还尝试从工作表宽度 + x 的最后一个块中获取工作表大小，但这仅在工作表已满时才有效。

我的问题又是如何获得每张纸的最终尺寸？

我有一个优化问题。这是关于包含 20 个零件的产品（生产顺序无关紧要）。我有 3 台类似的机器，可以生产所有 20 个零件。

我已经得到了以分钟为单位的 20 个部分（即生产第一部分需要 3 分钟，生产第二部分需要 75 分钟，等等）

因此，生产 1 个产品需要 730 分钟。

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

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

可能性很大 3^20

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

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

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

这个问题是关于任何代码或指针，这些代码或指针有助于在受约束且定义明确的网格内“接近”故事的布局。

这些是基础知识和输入：

• 整个对象被称为报纸。它有一组故事（文本长度不同）
• 每个故事可以有一个与之关联的图像，也可以没有
• 报纸会自动分成 4 栏。文本从左上到右下，每列向下流动
• 图像可以放置到固定位置 - 左上、中上、右上、左中、中、右中、左下、中下、右下
• 放置图像时，它可以跨越 1 到 3 列。根据设置的跨度自动调整高度以适应比例。
• 所有实际的布局工作（以及围绕文本流动的图像）都已完成 - 算法所需的只是决策制定

总的问题是将故事以一种有趣的方式放置在固定的布局中，使图片靠近与之相关的故事，并表现出有趣的位置和跨度变化，从而使印刷的阅读体验变得有趣和美观.

这是算法所需的工作：

• 当一个带有图片的故事被放到报​​纸上时，图片的至少一个边缘必须触及它所涉及的故事。
• 我们需要决定是否对故事进行重新排序，以便图像密度不会在一个区域过于偏颇，例如前 4 页有很多图片，而报纸的其余部分只是文字。
• 如果我们选择重新排序和打乱故事，那么解决这个放置问题的最佳方法是什么？

一般来说，我不确定这是否属于装箱问题——从某种意义上说，故事可以重新排序以最小化空白；因为我们需要将图像放置在故事“附近”。

任何有关如何解决此问题的指针或有助于解决类似问题的代码都将受到赞赏。

我有层次聚类树（使用链接）。每个集群在树状图中都有自己的级别，对应于该集群的成本。我有成本为 c1 的 n1 集群、成本为 c2 的 n2 集群和成本为 c3 的 n3 集群的预算。问题是使用预算选择哪个集群来覆盖所有原始项目。和 c1>c2>c3。成本为 c1 的集群显然可以用于 c2 或 c3 集群。

对于只有一个预算类别，解决方案很简单：只需从根开始，然后在每个子树中，当我们低于 c1 时添加它。如果 n1 个类别在子树之前完成，则没有解决方案。

对于两个类别，它也很简单。查找 c1 成本的所有候选者。用 c2 子集群的数量标记它们，并按降序对它们进行排序。选择具有最大标签的 c1 类别。然后选择 c2 集群。

但是对于超过 2 个类别的问题很复杂，因为对 c2 类别的排序不一定会跟踪 c3 预算。

我有一些容量不同的垃圾箱和一些指定大小的对象。目标是将这些对象打包到垃圾箱中。到目前为止，它类似于装箱问题。但扭曲的是，每个对象都与另一个对象有部分重叠。因此，虽然对象 1 和 2 的大小分别为 s1 和 s2，但当我将它们放在同一个 bin 中时，填充的空间小于 s1+s2。假设我知道每对对象的重叠值，是否也有任何近似算法，例如用于该问题的原始装箱算法？

我有一个图 G=(V,E) 边和节点都有权重。我想对该图进行分区以创建大小相等的分区。分区大小的定义是 sum(vi)-sum(ej)，其中 vi 是该分区内的一个节点，ej 是该分区内两个节点之间的一条边。在我的问题中，图表非常密集（几乎完整）。是否有任何近似算法？

这在某种程度上类似于 bin 包装中的问题，其中 bin 具有相同大小的重叠对象。节点的权重是它们的大小，边的权重显示两个对象可以重叠多少。

我有一个厨房从冷冻加热饭菜，他们需要按人数生产饭菜。餐点以冷冻大小的份量提供，例如 4 块、6 块等。较大的尺寸具有较低的单位成本。所以允许浪费，我如何计算尺寸以最低成本完成订单。

我有以下数字 6,8,9,4,3,2,10,7,14,12,6,2,3,1,10,11,13,5

我想知道为这些实现最适合的 1D Bin 打包算法的正确方法。因为在这个视频http://www.youtube.com/watch?v=B2P1TzKKWOI&feature=related他们解决它的方式与我的想法不同，所以我不知道正确的答案。

我的解决方案，先到先得，所以：

• 垃圾箱 #1：6,8,2
• 垃圾箱 #2：9,4,3
• 仓#3：3,10,1
• 箱#4：7,6
• 箱#5：14,2
• 垃圾箱 #6：12
• 垃圾箱 #7：10
• 垃圾箱 #8：11,5
• 9 号箱：13

他们的解决方案，我猜他们将合适的数字“配对”在一起，所以它就像：

• 垃圾箱 #1：6,10
• 垃圾箱 #2：9,7
• 仓#3：14,2
• 箱#4：12,4
• 箱#5：14,2
• 垃圾箱 #6：13,3
• 垃圾箱 #7：8,6,2
• 垃圾箱 #8：10,5,1
• 9 号箱：11,3

哪一个是正确的？