将不同大小的数据块打包到多个容器中
编辑：这个问题似乎被称为“切割库存问题”，
我需要一种算法来为我提供垃圾箱中块的（空间）最佳排列。一种方法是先将较大的块放入。但看看这个算法在这个例子中是如何失败的：
Chunks Bins
-----------------------------
AAA BBB CC DD ( ) ( )
Algorithm Result
-----------------------------
biggest first (AAABBB ) (CC )
optimal (AAACCDD) (BBB)
“最大的优先”不适合 DD。也许构建这样的表会有所帮助：
Size 1: ---
Size 2: CC, DD
Size 3: AAA, BBB
Size 4: CCDD
Size 5: AAACC, AAADD, BBBCC, BBBDD
Size 6: AAABBB
Size 7: AAACCDD, BBBCCDD
Size 8: AAABBBCC, AAABBBDD
Size 10: AAABBBCCDD
EDIT: It seems like this problem is called "Cutting stock problem"
I need an algorithm that gives me the (space-)optimal arrangement of chunks in bins. One way would be put the bigger chunks in first. But see how that algorithm fails in this example:
Chunks Bins
-----------------------------
AAA BBB CC DD ( ) ( )
Algorithm Result
-----------------------------
biggest first (AAABBB ) (CC )
optimal (AAACCDD) (BBB)
"Biggest first" can't fit in DD. Maybe it helps to build a table like this:
Size 1: ---
Size 2: CC, DD
Size 3: AAA, BBB
Size 4: CCDD
Size 5: AAACC, AAADD, BBBCC, BBBDD
Size 6: AAABBB
Size 7: AAACCDD, BBBCCDD
Size 8: AAABBBCC, AAABBBDD
Size 10: AAABBBCCDD
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这基本上是bin-packing问题的变体。众所周知，这个问题是 NP 困难的，因此不要指望为复杂情况（即具有许多对象和垃圾箱）找到有效的最优算法。
但是，如果您的对象/垃圾箱的数量相对较小，那么您可能只需使用 深度优先搜索。
这非常容易实现：只需取出第一个对象，然后递归地重新运行算法，将第一个对象依次放入每个容器中（即从可用容器空间中减去对象的大小）。最后，您只需要跟踪迄今为止找到的最佳“解决方案”，并在尝试了所有组合后将其作为最终答案返回。
您还可以通过以下方式使该算法运行得更快：
根据对问题大小的评论进行更新
鉴于您似乎有大量的块需要处理，您可能需要尝试以下操作：
This is basically a variant of the bin-packing problem. This problem is is known to be NP-hard, so don't expect to find an efficient optimal algorithm for complex cases (i.e. with many objects and bins).
However, if your number of objects/bins is relatively small, you will probably be fine just exhaustively searching all the possible combinations with a depth-first search.
This is pretty easy to implement: just take the first object, then recursively re-run the algorithm with the first object placed in each of the bins in turn (i.e. subtracting the size of the object from the available bin space). Finally, you just need to keep track of the best "solution" found so far and return this as your final answer once you have tried all combinations.
You may also be able make this algorithm algorithm run faster by:
Updated based on comments on problem size
Given that it looks like you have a very large number of chunks to deal with, you might want to try the following:
Mikera 是对的：这个多重 Knapsack 问题（装箱问题的变体）是 NP 硬。
以下是您的几个选择（从我对类似问题的回答复制而来）：
暴力，或者更好的是，分支定界。无法扩展（根本！），但会为您找到最佳解决方案（尽管可能在我们的有生之年找不到）。
确定性算法：按最大尺寸对块进行排序，并逐一遍历该列表，并为其分配最佳的剩余位置。这将很快完成，但解决方案可能远非最佳（或可行）。 这是一张很好的图片，展示了可能出错的示例。但是如果您想保持简单，这就是要走的路。
元启发式，从确定性算法的结果开始。这将在合理的时间内给你一个非常好的结果，比人类想出的更好。根据您投入的时间和问题的难度，它可能是也可能不是最佳解决方案。有几个库，例如 Drools Planner（开源 java）。
Mikera is right: this multiple Knapsack problem (a variant of the bin packing problem) is NP hard.
Here are a couple of your options (copied from my answer on a similar question):
Brute force, or better yet, branch and bound. Doesn't scale (at all!), but will find you the optimal solution (probably not in our lifetimes though).
Deterministic algorithm: sort the chunks on largest size and go through that list one by one and assign it the best remaining spot. That will finish very fast, but the solution can be far from optimal (or feasible). Here's a nice picture showing an example what can go wrong. But if you want to keep it simple, that's the way to go.
Meta-heuristics, starting from the result of a deterministic algorithm. This will give you a very good result in reasonable time, better than what humans come up with. Depending on how much time you give it and the difficulty of the problem it might or might not be the optimal solution. There are a couple of libraries out there, such as Drools Planner (open source java).
针对此问题的一般最佳算法尚不存在（请参阅装箱问题）。您可以在维基百科和/或谷歌搜索“装箱问题”上找到一些不同的方法，也许“背包问题”也会提供一些帮助。
A general best algorithm for this problem doesn't exist yet (see bin packing problem). You can find a few different approaches on wikipedia and/or googling for the "bin packing problem" and maybe "knapsack problem" would also provide some help.
Donald Knuth 的 Dancing Links 算法可以快速找到“精确覆盖”问题的解决方案。
Donald Knuth's Dancing Links algorithm is quick at finding solutions to "exact covering" problems.