打包算法
我有一组具有相关属性（重量、长度、宽度）的物品。 我还有一组包装类型，具有相关属性（最大重量、长度、宽度），
我正在寻找一种算法来确定将物品包装到的最少盒子数量。
到目前为止，我已经研究了背包问题，虽然它可以接近，但我并没有完全处理重量、价值类型的问题。
这是一个示例：
项目： 10 x 商品 #1，（每件 1 磅，24 英寸长，12 英寸宽） 5 x 商品 #2，（每件 2 磅，24 英寸长，6 英寸宽）
包装类型： 小盒子（最大重量 = 40 磅，24 英寸 x 12 英寸） 大盒子（最大重量 = 75 磅，24 英寸 x 24 英寸）
可能的包装方法是： 2x 小盒子 -> 每种项目类型一个 1x 大盒子 -> 其中的所有内容
我都想返回单个框结果，尽管如果我可以返回所有可能的组合，那也可以。
I've got a set of items, with associated attributes (Weight, Length, Width).
I've also got a set of Packaging Types, with associated attributes (Max Weight, Length, Width)
I'm looking for an algorithm to determine the LEAST amount of boxes to package the items into.
So far, I've explored the knapsack problem, and although it can come close, I'm not exactly dealing with a weight, value type problem.
Here's an example:
Items:
10 x Item #1, (1lb each, 24" long, 12" wide)
5 x Item #2, (2lb each, 24" long, 6" wide)
Packaging Types:
Small Box (MaxWeight = 40lbs, 24"x12")
Large Box (MaxWeight = 75lbs, 24"x24")
The possible ways to package this would be:
2x Small Box -> One for each item type
1x Large Box -> Everything in it
I would want to return the single box result, although if I could return all possible combinations, that would also work.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您正在描述装箱。 请注意，这个问题是 NP 困难的，因此如果不进行强力检查，您将无法获得最佳解决方案。 也就是说，在我看来，有些算法可以给你一个足够好的答案。
四处搜索最佳拟合递减和首次拟合递减的描述。
You're describing bin packing. Note that this problem is NP-hard, so you won't get the optimal solution without a bruce force check. That said, there are algorithms that get you, IMO, a good enough answer.
Search around for descriptions of best fit decreasing and first fit decreasing.
这是关于 3D 背包的有趣讨论问题。 这是一篇关于以下内容的论文同一个话题。
在类似的问题之后进行了类似的讨论。
Here's an interesting discussion of a 3D knapsack problem. Here's a paper on the same topic.
There was a similar discussion following a similar question.