问题标签 [bin-packing]

问题说，

给定一个大小为 n 的数组，我们必须将数组输出/划分为总和为 N 的子集。

我在 url Dynamic Programming3中看到了类似的问题/解释

我在pdf中有以下查询：-

1. 我们如何找到总和为 N 的子集，因为逻辑只告诉子集是否存在？
2. 另外，如果我们稍微改变一下问题，我们是否可以使用相同的意识形态找到两个具有相同平均值的子集？

任何人都可以对这个动态编程问题有所了解.. :)

提前致谢..

我正在尝试将字体字形图像打包到单个纹理中。位图是每像素单色 1 个字节，我希望将它们全部打包到 1 个纹理上。我能够计算出所需的最小纹理大小，但我无法管理一种算法将它们打包在一起。

我目前将位图存储为 char 指针，并且能够获取每个位图的尺寸。

我有一组不同大小的正方形和矩形，我想使用 PHP 将它们组合成一个大正方形/矩形。这些方块通常是我想制作成蒙太奇的图像——但有时它们只是数学对象。

是否有任何 PHP 算法，这种类型的东西叫什么？

更新：经过更多搜索，我认为我想要的是所谓的装箱问题。但是，我还想为某些类型的打包问题（如图像）添加一定量的随机化，以引起人们的兴趣。

我已经实现了一个类似于这里提到的矩形包装类。我的最终目标是将一些较小的精灵打包成一个大的精灵表。

我遇到的困难是想办法扩展该算法以允许静态矩形。即：在打包过程中位置保持静止并被有效视为要避开的障碍物的矩形。

我应该考虑另一种算法，或者可能是更有效的方法吗？

我正在寻找一种能够以最有效的方式解决我的问题的算法。

问题描述：

我有一个项目列表（只允许使用正整数）和固定数量的相同容量的垃圾箱。到目前为止，我考虑过分支定界算法，但我不太确定它是否是这种情况下的最佳方法。

例子：

给定一个项目列表：

和三个容量为 9 的箱子，我需要将它们打包：（物品的顺序无关紧要）

我认为这是装箱问题的一个变体（我知道这是 NP 完全问题），但由于我并没有试图最小化使用的箱数，我想知道是否有更好的解决方案。

我有一个 sql 查询，它选择具有最高权重的最佳小时组合，它使用递归 CTE 来查找所有小时组合，如下所示

然而问题在于，当行数增加迭代时。这需要很长时间。注意：- 请取消注释以上行以检查问题

对此的任何帮助将不胜感激

我真的很感激对这个实际问题的一些评论。

快速描述。 我有可变数量的链接，可用于构成给定的皮带宽度。问题是，每个链接有多少。选择标准：最好使用较长的项目。

例子。 假设我们要创建一个皮带宽度，W = 1024.0 其中一个模型具有以下链接长度：L = [34.0, 65.0, 96.0, 126.0]

问题是，每个链接有多少来制作宽度。

这是我尝试过的一些方法。

1.贪婪（选择最长的第一个以满足标准） c = [0,0,0,8] 其中c是每个项目的计数。这留下了 16.0 的差距，我什至无法容纳 1 个最小的项目。贪婪很容易，但并不好。

2. 选择循环 不太容易，我认为这是一个难题。我尝试了很多策略：填充小物品，然后依次移除它们以适应下一个尺寸。

3. 背包法 不太合适，因为这是基于给定数量的物品。

4. 子集和问题 这是背包的一个子类，但我无法让它工作。

5. 装箱问题 听起来很相似，但我无法将其应用于我的问题。

6.蛮力（随机选择） 奇怪的是，这个找到了很多完全匹配。我使用计数的简单多项式作为评级。rating = n[0] + n[1]* 2 + n[2] *3 + n[4]**4 + ... 蛮力的解决方案之一是 [4, 0, 4, 4] 给出正好是 1024。问题是，这种方法通常会产生不同的选择，因此并不理想。

7.穷举搜索 不实用，因为选择太多。

8. 模拟退火 从蛮力的成功来看，这看起来是一个不错的选择。有人可以给我举一个简单的例子吗（请不要是另一个旅行推销员）。

9. 遗传和粒子群 不确定这些。

现在，我陷入困境和沮丧。是否有可用于此问题的直接算法？

我正在寻找一种算法，可以帮助在更大的矩形内分布不同大小的矩形，同时最大限度地减少重叠。

我已经研究过装箱算法，但它们似乎最大限度地减少了矩形之间的空间量（在我的情况下，所有被打包的物品都是正方形）。

我想我想最大化所有正方形和外部矩形边界之间的距离。

这是我正在尝试做的一个例子：

我有一个算法可以根据某些条件进行装箱。我发现算法的流程对于读者来说有点复杂。

您可以在下面找到开发的 Java 代码。此代码是否有一个非常简化的替代流程？

笔记：

ptim-->现在时间

etim-->结束时间

限制-->限制

在 stackoverflow 上有一些类似的问题，但似乎没有一个提供一个对 NP-hard 问题和算法没有扎实理解的人可以理解的切实答案。

如何对矩形对象执行二维装箱？在我的情况下，我试图将几个图像组合成一个图像，用作精灵表，使用最少的空间。每个图像可能有非常不同的边界，但容器没有设置边界。

我希望了解装箱算法的人可以解释如何以编程方式实现这一点，而不是提供装箱方法的一般概述。