问题标签 [bin-packing]

这是我的问题：

• 有 n 家公司分销产品。
• 所有产品应在k天内分发
• Ci公司的产品分配应该是连续的-这意味着它可以在第2,3,4,5天分发，但不能在2,3,6,7天分发
• Ci 在第 j 天分发的产品数量应少于（或等于）第 j-1 天（如果在第 j-1 天有的话）
• 第 i 天和第 j 天分发的产品之间的差异不应大于 1

例子：

我们有 3 天的时间来分发产品。A公司的产品：a,a,a,a,a。B公司的产品：b,b,b。C公司产品：c,c

公平分配： [aab,aabc,abc]

无效分配： [aabc,aabc,ab] 因为第 1 天有 4 个产品，第 3 天有 2 个产品（差异 > 1）

无效分配： [abc,aabc,aab] 因为第 1 天有一个产品 A，第 2 天有 2 个产品 A，所以产品 A 的分配不是非递减的

编辑 如果存在无法进行公平分配的情况，请提供简短描述，我会接受答案

我知道我的问题可能没有“完美”的解决方案（这听起来像是背包或垃圾箱包装问题的变体），但这是我的场景：

我想将一个 SQL 数据库表列表划分为 n 个（比如说 7 个）大致相同大小的堆（这样我就可以将一些维护任务大致平均分布在整个一周内）。

假设我有 100 张桌子（可能更高或更低，但不可能高于 5000），大小从 1 到 10,000,000 不等（当然，更大的桌子不太常见）。

我最初的想法是按字母顺序（伪随机）对表格进行排序，然后从头开始，当总数超过 Sum(Size)/7 时移动到下一组。对于某些数据库，这可能会正常工作，但如果两个巨大的表彼此相邻，那么这会导致非常不平等的组。（这并不像听起来那么不可能，考虑两个巨大的表，Account_History 和 Account_History_Archive）。

是否有任何普遍接受的技术，可以为各种源数据提供“良好”的结果？我倾向于一种更简单的技术，而不是更精确的分组（如果某些日子的维护时间比其他日子稍长，那没什么大不了的）。

也许有人知道将石头（不同重量）放入不同大小的背包的算法，或者它有什么名字？我应该在 Prolog 中做到这一点。我给出了石头的重量和背包的容量。程序应该给我一个答案，我怎样才能把所有这些石头放进背包里。

我想做的是创建一个图像（在我的情况下为 2048x2048）该算法应该以这种方式工作：

-用户从文件夹中选择一些图像并告诉我的程序“生成图像”

- 程序检查是否可以将所有图像放在单个图像中（大小问题），否则返回错误消息

- 程序找到将所有图像放入图像中的正确方法，然后提示用户选择保存路径（显然旧图像不应调整大小/剪切）

问题显然是最后一步，我实际上不知道该怎么做，程序还应该检查另一件事，如果图像文件名是 myimage_1 并且有一个“myimage_2”，那么这些图像应该放在彼此附近（对于 3,4 等等，obiusly 相同）

有人可以帮我弄这个吗？

我希望我的标题有意义，但这是我想要做的：

我有n矩形，每个矩形的宽度为 W _n和高度为 H _n，我需要将它们排列在二维 (x,y) 平面上，它们都适合的矩形占用的面积最小。我还需要能够确定 (x,y) 对应于哪个矩形。

我更喜欢伪代码中的东西，但可以使用多种语言。

感谢您的帮助。

我有不同大小的对象包（很多对象可以具有相同的大小，例如：我有 54 个 6B 的对象、76 个 10B 的对象、79 个 24B 的对象等。

对象的大小为 6, 8 ,10 .... 字节）。我需要将该捆绑包打包成几条消息（每条消息的最大长度为 256 字节）。

问题是如何以最少的消息获得解决方案？

有什么已知的算法吗？我需要 Hopfield 神经网络吗？

给定n 个容量无限的垃圾箱，我想将m件物品装入其中（每个都有特定的重量），同时尽量减少最重垃圾箱的重量。

这不是一个传统的垃圾箱包装/背包问题，其中垃圾箱的容量有限，并且您试图尽量减少使用的垃圾箱数量；我有一定数量的垃圾箱，并且想全部使用它们以使最重的垃圾箱的重量尽可能低。

这个问题有名字吗？我浏览了许多带有关键词的论文，但我没有发现任何类似的东西。

干杯。

给定一组项目（大小从 1 到 100 的任意位置）和一些箱（1 到 15）。每个项目都有一个箱子集，该项目可以分配到，以及哪个箱最好、次佳、等等，只是为了它。项目也有自然顺序，下面用命名来表示，例如，项目 1 在项目 2 之前。每个箱子的容量在 1 到 5 之间（每个物品的重量相同，即 1。）

示例输入可以是三个箱子和六个物品（- 表示箱子不在物品的可用集合中，即不能与它一起打包）：

目标是（为了在发生冲突时每个目标完全覆盖任何较低的目标，例如，无论使用多少箱或忽略偏好，打包五个物品总是优于四个）：

1. 最大化包装的物品数量
2. 按自然顺序包装物品，例如，如果总箱容量为 1 并且有两个物品，则将包装 item1 而 item2 不包装
3. 最小化使用的垃圾箱数量
4. 根据每个项目的 bin 偏好和自然顺序打包每个项目，即第一个偏好中的 item1 和第二个中的 item2 优于第二个中的 item1 和第一个中的 item2
5. 在两个解决方案无法通过这些目标区分的情况下，任何一个解决方案都可以接受更高的排名，例如，作为实施的副作用或只是任意的平局。

所以上面的输入将被打包为：

然后的问题是阅读/审查什么来帮助我想出解决这个问题的算法想法，第一段的输入大小和几秒钟的时间限制，即不是蛮力（或至少任何蛮力到目前为止我已经想到的力量。）我正在使用 Ruby 和 C，但是在这个林木蹒跚的阶段，语言并没有过度相关。

我将不胜感激任何阅读建议、关于算法组合的想法，或者只是关于澄清问题陈述的想法......

更新 1

不太清楚，虽然有许多算法涵盖了这方面的各个部分，但我的困难在于找到（或可能识别）一起处理所有标准的信息，特别是在容量过剩和项目冲突时尽量减少使用的垃圾箱数量-bin 设置和项目偏好，希望在以下示例中更清楚地显示：

虽然 bin1 是最首选的，但 item3 根本不能放在其中，而 bin2 是所有项目的第二首选，它只能容纳三个项目中的两个。所以正确的赋值集 (x) 实际上是最不喜欢的 bin：

更新 2 我用有关目标如何关联的信息重新编写了描述，并删除了 bin 优先级变量，因为它只会降低找到答案的可能性，并且可以在我正在处理的系统的其他地方解决。

我正在开发一款俄罗斯方块类型的 HTML5 游戏，需要加强空间优化算法。需要以最节省空间的方式将不同大小的矩形块添加到画布中。我知道块占用了多少空间，我需要找到可以使用固定 x 坐标添加块的最近点——绝对最近的点是一个不错的选择。

我已经实现了一个版本，它使用画布上的逐个像素值检查进行搜索，该画布向下推，直到找到足够的可用空间来放置形状，然后添加它。这仅在空间从左到右填充时（缓慢）起作用-算法可以安全地假设如果第一个像素列是安全的，则可以添加整个块。

我需要使它更健壮，这就是我认为应该去的地方。

存储一个四叉树来表示棋盘状态让我可以更快地确定哪里有空间。

每个深度级别存储 4 个节点——每个节点要么是 0 表示完全为空，要么是 1 表示“在某处有一些东西”。每个渐进的深度级别都提供了有关董事会的越来越多的信息。

表示网格的最佳 javascript 数据结构是什么？

到目前为止我考虑过的事情：

A. 构建一个完整的tree对象，其中包含指向子对象和值的指针以及一组导航它的方法。这将是直观的并且可能节省空间，但我怀疑速度非常慢。

B. Look at each grid as 4 bits and store the depths as hex arrays or objects. If done by a person more clever than myself, this probably optimizes not just the storage but makes clever bit operations available to compare adjacent cells, turn blocks on and off, etc. I imagine it would be incredibly fast, incredibly efficient, but it's beyond my skills to build.

C. Store each depth in an array. Depth[0]=[1,0,0,0]; Depth[1][1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0] etc. This is where I'm headed at the moment. It's not very space efficient and it probably won't be incredibly fast, but I think I can get my head around it.

There's a practical limit to any structure to the number of depths (the array to store availability of 4x4 spaces in my last approach is more than 65 thousand) after which making the expensive call to check the last few pixels of image data from the canvas with a regular iterator is unavoidable.

So, A,B,C, other?

As usual, all insights appreciated.

我曾经开发过用木头、玻璃、石头等材料制造东西的软件，并提供了自动布置零件的方法，从而最大限度地减少浪费。你们中的许多人都知道这是装箱问题。我偶然发现了这个 - http://www.dropbox.com/jobs/challenges#packing-your-dropbox - 发现这个问题很有趣。

磁盘空间通常被认为是一维数组，文件被分开以适应彼此。然而，在这里，它们是不重叠的矩形。我使用了一个应用程序 Disk Inventory X，它使用相同的概念来进行文件系统可视化。

请原谅我的无知和无法正确构建谷歌查询，有人可以解释一下，这与现实世界的实现有什么关系？

假设这是文件在磁盘上的布局方式，那么现实世界对输入数据和消耗的时间/内存的要求是什么？

非常感谢！