问题标签 [bin-packing]

问题陈述：您有 n1 件尺寸为 s1 的物品，n2 件尺寸为 s2 的物品，以及 n3 件尺寸为 s3 的物品。您希望将所有这些物品装入每个容量为 C 的箱子中，以使使用的箱子总数最小化。

我的解决方案：

上述解决方案仅有效地填充单个箱。有人可以建议如何修改上述关系，以便我有效地获得用于包装物品的总箱吗？

编辑已找到解决方案！

这是一篇关于它的博客文章，这里是Github repo！

我正在创建一个由多个大小的框组成的 div 网格，这些大小是设置的高度和宽度 - 但是是动态生成的，因此每次加载页面时都会有一个不同的网格。

我的问题-我尝试使用 Masonry，但最终留下了空隙，还尝试了同位素。我目前正在浮动导致布局中断的元素。

它是如何构建的——我计算屏幕尺寸并确定从 1 到 6 的页面的最佳列数，然后根据该列宽我计算一个“块”，这个块基本上是完美的网格。然后我遍历我的元素并给它们 1x1、1x2、2x2 尺寸。

作为参考，这里是另一个随机生成的网格

我的问题- 有没有一种很好的方法来检测丢失的空间 - 目前我将红色和黑色的盒子放在另一个绿色的“块”网格上，让我看看我在哪里丢失了空间。我已经阅读了有关背包包装问题以及垃圾箱包装问题的信息——我很难理解其中任何一个问题。

我尝试过的- 我试图在放置块以确定最佳尺寸时进行计算，但这仍然会导致奇怪的行为。我也尝试过使用砖石和同位素。

我对参差不齐的底部边缘很好，但实际的网格不能包含任何间隙。

注意- 网格由可能无穷无尽的元素组成 - 我一直在考虑是否要从底部区域获取并复制一个元素并将其放置到丢失的区域中，我可以避免不得不“移动”元素 - 我只是需要知道如何找到那个缺失的空间。

任何帮助或指向正确的方向都会很棒！

这是一个jsfiddle

这是js的基本代码...

我正在寻求帮助以改进放置奇怪形状块的算法。我的问题域很奇怪，但我的块最好的类比是俄罗斯方块，除了它们可以有四个以上。这些块仍然仅由直角组成，但它们可以是长而弯曲的，它们可以分支，等等。

我试图在最小的空间中安排多个任意形状的大块（我知道，一个装箱问题），但我目前的解决方案看起来很难看。我基本上是放置一个，然后通过尝试将它们放置在我的网格的原点来强制其余的，然后慢慢地将它们推向不同的方向，直到它们不再碰撞。它并不慢，但它并没有尝试很好地安装部件，因此它们不会浪费整体空间。

我唯一能想到的尝试是按大小对积木进行排序，首先放置最大的，然后将最小的放在最后的任何孔中。但肯定有一些方法会适得其反。

有什么启发式或近似算法可以帮助我吗？

结果如下所示：

另外，也许我的 gravatar 表明这与洛克人有关……

我有一个大矩形（面向轴），其中包含许多小矩形（与父级的方向相同，固定大小为 82x176 像素）。

现在我有一个在外面的小矩形，我必须把它放在大矩形里面，这样它是： - 随机放置；- 除非由于空间不足（在这种情况下，重叠最小），否则不要与其他小矩形重叠。

该算法将在我的代码执行期间多次使用，还需要包括一个良好的分布，以便小矩形将很好地分散在大矩形的中心周围，而不是全部聚集在一个角落。

谷歌搜索，我发现了几种关于矩形打包、最大空矩形、随机分布的算法......但没有什么能真正满足我的要求，也没有显示出良好的代码实现。

有没有人有什么好主意（代码或伪代码更好，如果可能的话，通常当我看到数学公式时我的大脑会崩溃）？

我有这个 Bin 包装代码：

这工作正常，但有一个问题：

如果我在 C# 中定义：

结果是：

但是如果我只是将数组中元素的顺序更改为

结果将是：

问题是：

如何对酒吧进行最佳优化？

最佳优化是元素的总和，直到最大尺寸，其余部分较少。

在上述情况下很容易。

但如果我有：

结果将是：

许多酒吧和全损

但是如果我这样排列数组：

结果是：

这是最好的解决方案！

有任何想法吗？

我使用最佳拟合方法为装箱问题编写了一个启发式算法，itens S =（i1，...，in），箱大小 T，并且想要创建一个真正的精确指数算法，以计算最佳解决方案（最小包装所有物品的箱子数量），但我不知道如何检查包装的每一种可能性，我在 C 中做。

有人可以告诉我任何想法我必须使用哪些结构？我怎样才能测试itens的所有de组合？它必须是递归算法吗？有一些可以帮助我的书或文章吗？

对不起，我的英语不好

今天我第一次使用 Android 4.2，我注意到主屏幕如何在您拖动小部件时自动重新定位它们：

我最近为我们的项目编写了一个类似的代码，我不得不承认它的性能要差得多。我的算法真的很愚蠢，我正在寻找更好的替代方案。这是我找到的最接近的一个，但我还没有测试过。

据我了解，这与装箱有关，但装箱算法侧重于将矩形彼此尽可能靠近，而 Android 实现侧重于对初始配置进行尽可能少的更改，因此美观。

因为 Android 是开源的，所以我希望从他们的代码中学习，但是我找不到任何与在android.appwidget. 看什么地方合适？

我有一个矩形，需要在其中动态放置和删除较小的矩形。这基本上是垃圾箱包装问题，但也允许物品移除。

由于成本原因，我无法在每次删除后重新创建所有内容（这会使复杂性呈指数级增长）：我需要动态添加和删除矩形。此外，移动已经放置的矩形并不简单（因此我会避免它），尤其是移动放置在给定矩形之后的所有矩形不是一个选项。

我需要一个 C++ 实现，但如果它不可用，只需一个算法就可以了。

我有一个 200 宽和 100 高的矩形。我有一个由 50 个矩形和盒子组成的混合池。矩形有 20x40 和 40x20 等形状。这些盒子的形状为 20x20 和 40x40。因此，假设我想在这个更大的矩形中放置最多数量的框和矩形，以便不留空间。除了 bin 打包算法或矩形打包算法之外，我如何实现它。如果我应该选择其中一种算法，是否有适合这种情况的良好实现？

我正在为装箱问题研究不同的启发式解决方案，并实现了不同的算法，如 FF、FFD、BF、BFD 等。我的问题是，有没有比这些更好的算法，或者这些算法是否有任何（甚至很小的）改进。我读了很多书并搜索了这个，但找不到真正有趣的东西。