This is a Bin Packing problem, and it's NP-hard. For small number of objects and packages, you might be able to simply use the brute force method of trying every possibility. Beyond that, you'll need to use a heuristic of some sort. The Wikipedia article has some details, along with references to papers you probably want to check out.
The alternative, of course, is to start with a really simple algorithm (such as simply 'stacking' items) and calculate a reasonable upper-bound on shipping using that, then if your human packers can do better, you make a slight profit. Or discount your calculated prices slightly on the assumption that your packing is not ideal.
The literature on "3D Bin packing" is far and wide. You can get a good overview by tracking the publications of Professor David Pisinger. He also published one of the few high quality implementations of bin packing with sourcecode: 3dbpp.c
My own logistics toolkit pyShipping comes with a 3D Bin Packing implementation for Warehousing applications. It is basically implementing 4D Bin Packing (3D size & weigth) and gets an acceptable solution for typical order sizes (a few dozens of packages) in under a second runtime. It is used in production (meaning a warehouse) for some months now to determine the upper bound of shipping crates to be used. The warehouse workers are often able to pack somewhat more efficiently but that's OK with me.
Are you trying to see how many of a single type fits into a particular sized package, or are you trying to mix types as well?
Sounds like you're trying to solve the Knapsack Problem. You might be able to find some algorithms for that which could be adapted to your specific requirements. Just understand that it will be hard to find an efficient algorithm, as the problem is NP complete (though depending on your specific requirements you may be able to find an efficient approximation, or your inputs may be small enough that it doesn't matter).
这可能会导致您的包装工来询问如何以编程方式将 n 个物品包装到 m 个盒子中。 :-P （他们也可能会要求你去做，向你寻求指示，等等）。
只要你的算法能做到正常人会做的事情，我个人就会接受它的运输估算。
If the boxes are to be hand packed, then you might consider writing an algorithm which would do what a reasonable human would do. The reason I suggest this is because unless you want to print out packing instructions for each order, then whoever is doing your packing is going to have to workout how they are going to fit the ordered items in however many boxes it has been allocated for the order.
This might then lead to your human packers coming to SO asking on how to programmatically workout how to pack n items into m boxes. :-P (They might also ask you to do it, ask you for instructions, etc).
As long as your algorithm does what a reasonable human being would do, I would personally accept its shipping estimate.
Metaheuristics are good to deal with real world bin packing problems when there are many packages and/or many constraints. One open source Java implementation is Drools Planner.
Maybe this will sound obvious, but it might be worthwhile to memoize the problem, then do some of them by hand. Finding a most effecient solution for arbitrary inputs and boxes in NP-hard, but by restricting the problem space, and accepting some inefficiency, that NP size might be something reasonable, and by memoizing, you might be able to bring the "common-case" time down substantially.
It might also help to think about things in terms of hierarchical packing.
After lot of searching i have found a GitHub repository that might help someone. Function PackingService.Pack() takes list of Container and list of Item(s) to be packed as parameter and return result which contains lot of information including
"container(s) packed in percentage and list of packed and unpacked items"
发布评论
评论（8）
这是一个 Bin Packing 问题，并且是 NP 难问题。 对于少量的对象和包，您可以简单地使用暴力方法来尝试每种可能性。 除此之外，您还需要使用某种启发式方法。 维基百科文章提供了一些详细信息，以及您可能想要查看的论文参考。
当然，另一种选择是从一个非常简单的算法（例如简单地“堆叠”物品）开始，并使用该算法计算合理的运输上限，然后如果您的人工包装员可以做得更好，您就会获得微薄的利润。 或者假设您的包装不理想，稍微折扣您的计算价格。
This is a Bin Packing problem, and it's NP-hard. For small number of objects and packages, you might be able to simply use the brute force method of trying every possibility. Beyond that, you'll need to use a heuristic of some sort. The Wikipedia article has some details, along with references to papers you probably want to check out.
The alternative, of course, is to start with a really simple algorithm (such as simply 'stacking' items) and calculate a reasonable upper-bound on shipping using that, then if your human packers can do better, you make a slight profit. Or discount your calculated prices slightly on the assumption that your packing is not ideal.
关于“3D Bin Packing”的文献非常广泛。 您可以通过跟踪 David Pisinger 教授。 他还发布了少数几个高质量的装箱源代码实现之一： 3dbpp.c
我自己的物流工具包 pyShipping 带有 3D仓储应用程序的装箱实施。 它基本上实现了 4D Bin Packing（3D 尺寸和重量），并在第二个运行时间内获得典型订单尺寸（几十个包裹）的可接受的解决方案。 它已在生产（即仓库）中使用了几个月，以确定要使用的运输箱的上限。 仓库工人通常能够更有效地打包，但这对我来说没问题。
The literature on "3D Bin packing" is far and wide. You can get a good overview by tracking the publications of Professor David Pisinger. He also published one of the few high quality implementations of bin packing with sourcecode: 3dbpp.c
My own logistics toolkit pyShipping comes with a 3D Bin Packing implementation for Warehousing applications. It is basically implementing 4D Bin Packing (3D size & weigth) and gets an acceptable solution for typical order sizes (a few dozens of packages) in under a second runtime. It is used in production (meaning a warehouse) for some months now to determine the upper bound of shipping crates to be used. The warehouse workers are often able to pack somewhat more efficiently but that's OK with me.
Pisinger 是少数发布工作代码的学者之一。 在他的一篇论文中，他提到了“最小深度”问题。
这是一个实用且高效算法 用于 3D 矩形盒包装，可调整封闭盒的高度。
这是 php 中的实现。
Pisinger is one of the few academics who posts working code. In one of his papers he mentions the "Minimum Depth" problem.
Here is a practical and efficient algorithm for 3D Rectangular Box Packing that adjusts the height of the enclosing box.
And here is an implementation in php.
您是否想看看有多少单一类型适合特定尺寸的包装，或者您是否也尝试混合类型？
听起来您正在尝试解决背包问题。 您也许能够找到一些适合您的特定要求的算法。 只要明白，很难找到一个高效算法，因为问题是 NP 完全的（尽管根据您的具体要求，您也许能够找到一个有效的近似值，或者您的输入可能足够小）这并不重要）。
Are you trying to see how many of a single type fits into a particular sized package, or are you trying to mix types as well?
Sounds like you're trying to solve the Knapsack Problem. You might be able to find some algorithms for that which could be adapted to your specific requirements. Just understand that it will be hard to find an efficient algorithm, as the problem is NP complete (though depending on your specific requirements you may be able to find an efficient approximation, or your inputs may be small enough that it doesn't matter).
如果要手工包装盒子，那么您可能会考虑编写一个算法来完成理性人会做的事情。 我建议这样做的原因是，除非您想打印每个订单的包装说明，否则无论谁负责包装，都必须考虑如何将订购的物品装入已分配给该订单的多个盒子中。命令。
这可能会导致您的包装工来询问如何以编程方式将 n 个物品包装到 m 个盒子中。 :-P （他们也可能会要求你去做，向你寻求指示，等等）。
只要你的算法能做到正常人会做的事情，我个人就会接受它的运输估算。
If the boxes are to be hand packed, then you might consider writing an algorithm which would do what a reasonable human would do. The reason I suggest this is because unless you want to print out packing instructions for each order, then whoever is doing your packing is going to have to workout how they are going to fit the ordered items in however many boxes it has been allocated for the order.
This might then lead to your human packers coming to SO asking on how to programmatically workout how to pack n items into m boxes. :-P (They might also ask you to do it, ask you for instructions, etc).
As long as your algorithm does what a reasonable human being would do, I would personally accept its shipping estimate.
当存在许多包裹和/或许多约束时，元启发式方法可以很好地处理现实世界的装箱问题。 一种开源 Java 实现是 Drools Planner。
Metaheuristics are good to deal with real world bin packing problems when there are many packages and/or many constraints. One open source Java implementation is Drools Planner.
也许这听起来很明显，但记住这个问题，然后手工做一些可能是值得的。 为 NP-hard 中的任意输入和框找到最有效的解决方案，但通过限制问题空间并接受一些低效率，NP 大小可能是合理的，并且通过记忆，您可能能够带来“常见情况” “时间大幅缩短。
从分层包装的角度思考问题也可能有所帮助。
Maybe this will sound obvious, but it might be worthwhile to memoize the problem, then do some of them by hand. Finding a most effecient solution for arbitrary inputs and boxes in NP-hard, but by restricting the problem space, and accepting some inefficiency, that NP size might be something reasonable, and by memoizing, you might be able to bring the "common-case" time down substantially.
It might also help to think about things in terms of hierarchical packing.
经过大量搜索后，我找到了一个 GitHub 存储库，可能会对某人有所帮助。 函数
PackingService.Pack()将要打包的Container列表和Item列表作为参数，并返回包含大量内容的结果信息包括“集装箱包装百分比以及包装和未包装物品清单”
After lot of searching i have found a GitHub repository that might help someone. Function
PackingService.Pack()takes list ofContainerand list ofItem(s) to be packed as parameter and return result which contains lot of information including"container(s) packed in percentage and list of packed and unpacked items"