问题标签 [bin-packing]

我正在开发一个在 Java中实现“全箱打包”算法的项目。这个算法名称来自决策 A-Level Maths - 但我在互联网上找不到太多关于它的信息。

算法描述如下：

• 使用观察来找到可以装满垃圾箱的物品。先把这些东西打包。
• 使用 first-fit 算法（我已经为其编写了方法）来打包其余的项目。

所以我有两个问题：

1. 这与所谓的“最佳拟合”算法相同吗？
2. 如何在程序中实现这一点？（具体来说，找到可以填满垃圾箱的组合的最佳方法是什么？）

在我的程序中，项目将是数字，并且最大数字数和 bin 数都将限制为 6。

我实际上还没有编写任何代码，因为我不确定如何首先实现它 - 但我编辑了第一篇文章以展示我正在考虑的一种方式。

编辑 - 假设我拥有的 6 个数字是：{1、2、3、4、5、6}。

我想到的方法是首先将数字按降序排序，然后有 2 个循环来尝试所有可能的组合，看看它们中的任何一个是否填满一个箱子（例如 1 & 2、1 & 3、1 & 4、1 & 5, 1 & 6 然后是 2 & 3, 2 & 4 等等），这是一个好方法吗？

我发布了与此问题类似的内容，但在实现代码时遇到了麻烦。

我有一个 python 程序，它从 HTML 文件中收集数据，包括重量、价格、书名等。我想把书分类成“n”个包，每个包不超过 10 磅。我可以毫无错误地运行该程序，它会提取信息，但我没有得到任何打包结果。

这是我的代码，有人可以给我建议吗？

我正在寻找一个求解器来解决 2D 装箱问题。我看过几篇建议“二叉树算法”的帖子，但我有大约 200,000 个 bin，所以我不确定该算法是否可扩展。

我在想古罗比。但我不知道如何在 Gurobi 中建模问题。有人知道我可以使用的任何可用模型吗？或者是否有任何可用的java代码，可以给我一个“接近精确”的解决方案，考虑到它是NP难的事实？

谢谢

/米娜

我正在解决一个问题，该问题涉及需要将一组固定的物品打包到固定数量的箱子中，每个箱子都有不同的容量。

保证所有物品都可以装入固定数量的箱中，不会有剩余容量。

一个很好的例子是拥有有限数量的硬币和两个不同的余额，并试图找出哪些硬币形成了哪个余额。

我知道装箱是 NP 难的，但我想知道这个问题是否有比我一直使用的贪婪算法更好的近似解决方案。

问题：
我们有N台物理机（PM），每个都有 ram R _i，cpu C _i和一组当前调度的 VM，每个 VM 分别具有 ram 要求ri和c i_将 任何 VM 从一个 PM 移动（迁移）到另一个有成本关联的取决于它的 ram r _i。关闭没有 VM 的 PM 以节省电力。 我们的目标是通过迁移一些虚拟机来最小化（N，迁移成本）的加权和，即最小化工作 PM 的数量以及不因过度迁移而降低服务水平。

我的方法：
蛮力方法是选择最小负载的 PM，并尝试通过首先拟合递减算法将其 VM 拟合到其他 PM，或者我们可以根据负载水平选择受害 PM 和目标 PM，并在可能的情况下通过移动它们来关闭受害者虚拟机到目标。我在Baadal
数据（IIT-D 云）上尝试了这种贪婪方法，但它并没有给出有希望的结果。

我也曾尝试研究动态VM整合的蚁群优化，但无法理解。我使用了链接。
http://dumas.ccsd.cnrs.fr/docs/00/72/52/15/PDF/Esnault.pdf http://hal.archives-ouvertes.fr/docs/00/72/38/56/PDF /RR-8032.pdf

有人请澄清解决方案或建议任何新方法/资源以获得更好的性能。
我基本上是在寻找算法而不是物理优化，我也知道许多商业组织已经提供了这些解决方案，但我只是想了解更多底层算法。

提前致谢。

我有一个听起来像是典型的装箱问题：x个不同尺寸的产品需要装进y个不同容量的容器中，从而最大限度地减少使用的容器数量，同时最大限度地减少浪费的空间。

我可以简化问题，因为产品尺寸和容器容量可以减少到标准的一维单位。即这个产品是 1 个单位大，而那个是 3 个单位，这个盒子有 6 个单位，那个 12 个。想想鸡蛋和纸箱，或啤酒箱。

但是还有一个额外的限制：每个容器都有一个特定的属性（我们称之为color），每个产品都有一组与之兼容的颜色。颜色和产品/容器尺寸之间没有相关性；一种产品可能与整个调色板颜色兼容，另一种产品可能仅与红色容器兼容。

这个问题变体是否已经在文献中描述过？如果有，它的名字是什么？

有一大堆对象。集合是动态的：可以随时添加或删除对象。我们称对象总数为N。

每个对象都有两个属性：上次更新的质量 ( M ) 和时间 ( T )。

每X分钟应该选择一小批进行处理，这会将它们的T更新为当前时间。批次中所有对象的总M是有限的：不超过L。

我希望在这里解决三个任务：

1. 找到下一批对象拾取算法；
2. 引入对象类：简单、优先（至少适合每个第 n 个批次）和频繁（适合每个批次）；
3. 预测系统容量耗尽（添加下一个服务器的时间 = 增加L）。

什么样的模型最能描述这样的系统？

整个事情是关于按时间间隔处理“对象”的服务。每个对象应每 N 小时“测量”一次。N 可以在一个范围内变化。X是固定的。

对象由人类添加/删除。N呈指数增长，相当缓慢，有一些由出版物引起的峰值。当然预测不能准确，只是一些估计。M在 0 到 1E7 之间变化，呈指数分布，大多数接近于 0。

我看到这里可以有几种策略：

A.全油门——每批包装尽可能接近 100%。随着N的增长，特定对象被击中的平均间隔将会增长。

B.平等的气质:) - 尝试将平均间隔保持在某个值附近。批次填充水平将从某个低水平增长。当它接近 100% 时——是时候获得更多服务器了。

C. - ?

这个问题的灵感来自另一个关于进程分配的问题。这是对那里讨论的问题的一种扭曲和增强。

我们有n 个进程，我们需要将它们分配给尽可能少的处理器。每个进程都有一个预定的开始和结束时间，我们将根据时间单位来定义，从 1 开始索引；一个进程将运行一些连续的时间单位序列。然后可以调度处理器运行任意数量的非重叠进程。

明显的贪心算法是：

在每一步，将剩余进程的最大不重叠集调度到下一个处理器上。

如何选择最大不重叠集？我们将算法保留为non-deterministic，因为这样更容易分析和拆分为两个子问题。

本质上，前一个问题涉及算法不走运时的行为：该算法可能产生次优分配的最小n是多少（即，需要比必要更多的处理器）？事实证明，答案是n = 4。在某些情况下，两个处理器就足够了，但贪心算法可能需要三个处理器（尽管如果幸运的话，它会分两步完成）。

这个问题涉及如果非确定性总是幸运的会发生什么：

保证该算法次优的最小n是多少？也就是说，我们可以找到一组进程的最小n是多少，其中贪心算法必须使用比必要更多的进程？

由于 Stack Overflow积极鼓励提出和回答你自己的问题，所以我会在这里这样做，你可以告诉我我的部分答案是否可以改进！

我正在研究一个问题，它是装箱的一种变体，但有一些更一般的形式，有额外的限制。问题定义如下——

我们有不同大小的对象，可以将它们分组到对象类中。我们有容量不同的垃圾箱，它们也被分为垃圾箱类（同一类中的所有垃圾箱都具有相同的容量）。对象类对它们可以放入哪些箱有限制——例如，“A”类的对象可以放置在“X”或“Y”类中的任何一个中。目标是找到每个类中的最小箱数，这可以产生给定对象集的最佳包装。

这个问题是否有一个很好的数学公式，以及您遇到的解决方法？这是可以应用相同方法的装箱问题的扩展吗？我知道这很难 NP。我找不到太多关于如何解决这个问题的信息，所以如果你能指出我正确的方向，那将非常有帮助。

我有 100 个组，每个组里面都有一些元素。对于交叉验证，我想制作五个大小尽可能相等的箱子。

有没有为此目的的算法。

5 个组和 2 个箱的示例：

这两个垃圾箱将是：

G1 和 G2 -> 它们的和等于 11。

G3、G4 和 G5 -> 它们的和等于 10。