问题标签 [bin-packing]

有谁知道现有的软件或算法来计算运送多件物品的包裹大小？

我在我们的库存数据库中有一堆项目，定义了长度、宽度和高度尺寸。鉴于这些尺寸，我需要计算有多少购买的物品适合预定义的盒子尺寸。

我正在寻找用于矩形和/或不规则形状的 2d bin 打包的开源（最好是 c++）算法。我找到了几篇关于这个主题的论文，但没有代码。

我正在寻找任何 3d bin 打包算法的确定性实现，即将许多不同的小方体打包到一个或多个更大的长方体中。解决方案可能与最佳解决方案不同。

它应该用 C、C++、Java、C#、IronPython、IronRuby 或任何其他可以从 .Net 代码中提取的语言编写。

我找到了这个 C 算法http://www.diku.dk/hjemmesider/ansatte/pisinger/3dbpp.c，但它不会旋转长方体来找到最合适的。我可以不将它们倒置旋转，但水平旋转应该是可能的。

我已经实现了 First-Fit-Decreasing bin 打包算法，将数字列表拆分为两个大小相等的“bin”。该算法几乎总能找到最佳包装安排，但有时却找不到。

例如：

数字 4, 3, 2, 4, 3, 2 的集合显然可以拆分成这样的排列： 1) 4, 3, 2 2) 4, 3, 2

第一次拟合递减算法找不到解决方案。

在这种情况下，不找到正确的解决方案（如果存在）是不可接受的。

最初的难题是将一个数字序列分成两个总和相等的集合。

这只是一个简单的装箱问题还是我使用了错误的算法？

我面临一个 3 维装箱问题，目前正在对哪些算法/启发式目前产生最佳结果进行一些初步研究。由于问题是 NP 难题，我不希望在每种情况下都能找到最佳解决方案，但我想知道：

1）什么是最好的精确求解器？分支和绑定？我可以期望通过合理的计算资源解决哪些问题实例大小？
2）什么是最好的启发式求解器？
3) 有哪些现成的解决方案可以进行一些实验？

我需要生成三行文本（基本上是乱码），每行 60 个字符长，包括每行末尾的硬回车。这些行是从各种长度（通常为 1-8 个字符）的单词字典中生成的。任何单词都不能使用超过一次，并且单词必须用空格分隔。我认为这本质上是一个装箱问题。

到目前为止，我采用的方法是创建单词的 hashMap，按它们的长度分组。然后我选择一个随机长度，从地图中拉出一个该长度的单词，并将其附加到我当前生成的行的末尾，考虑空格或硬返回。它大约有一半的时间有效，但另一半的时间我陷入了无限循环并且我的程序崩溃了。

我遇到的一个问题是：当我在行中添加随机单词时，给定长度的单词组可能会耗尽。这是因为字典中每个长度的单词数量不一定相同，例如，可能只有一个长度为 1 的单词。所以，我可能需要一个给定长度的单词，但不再有该长度的任何可用单词。

以下是我到目前为止的摘要。我正在使用 ActionScript，但希望能以任何语言深入了解这个问题。提前谢谢了。

我一直对编写一个应用程序感兴趣，该应用程序将展示如何在容器中安装（随机尺寸的）盒子，以便尽可能少地留下空间。一个现实生活中的例子将告诉您如何利用 UPS 卡车中的最大空间。有谁知道这样的事情开始的好地方？是否存在与我正在谈论的类似的现有算法？

我想知道是否有人知道任何适合将 N 个未知大小的矩形组合成尽可能小的包含矩形的算法。

最佳我的意思是减少生成的包含矩形中剩余的空白量。

我想用它从一系列图像中生成 css 精灵。

非常感谢，

伊恩

这是我第一次使用这个网站，很抱歉有任何错误的格式或奇怪的公式，我会尽力遵守这个网站上的规则，但我一开始可能会犯一些错误。

我现在正在使用 STL 容器在 C++ 中实现一些不同的 bin 打包算法。在当前代码中，我仍然有一些需要修复的逻辑错误，但这个问题更多的是关于程序的结构。对于如何构建程序以尽量减少逻辑错误的数量并使其尽可能易于阅读，我不希望有第二意见。在目前的状态下，我只是觉得这不是最好的方法，但我现在真的没有看到任何其他方法来编写我的代码。

该问题是一个动态在线装箱问题。从某种意义上说，它是动态的，即物品在离开分配给它们的箱之前有任意时间。

简而言之，我的问题是：
Bin 打包算法的结构在 C++ 中的外观如何？
STL 容器是使实现能够处理任意长度输入的好工具吗？
我应该如何以一种好的、易于阅读和实施的方式处理容器？

关于我自己的代码的一些想法：
使用类在处理不同箱的列表和这些箱中的项目列表之间做出很好的区分。
使实施尽可能有效。
易于运行许多不同的数据长度和用于基准测试的文件。

请注意，这只是我的代码的快照，尚未正常运行

不想用无关的喋喋不休把这个弄得乱七八糟，只想感谢做出贡献的人，我会检查我的代码，希望能够更好地构建我的程序

我正在尝试解决一个问题（在 php 中，但编程语言无关紧要）。我有n个人支付了钱，我有m个人将支付与n个人支付的总和相同的金额。我想计算这些人之间的最短汇款路线。可以拆分付款并支付给不同的人。理想的情况是一个人只进行一两次交易。有人可以指出我正确的方向或帮助我吗？

示例：A 支付了 100 美元

B 人支付了 200 美元

C 人支付了 50 美元

D 将支付 24 美元

E 人将支付 175 美元

F 人将支付 151 美元

一种可能的解决方案是

E 人向 A 人支付 100 美元，

E 人向 B 人支付 75 美元，

F 人向 B 人支付 125 美元，

F 人向 C 人支付 26 美元

D 人向 C 人支付 24 美元