将产品分配到盒子的算法 [英] Algorithm for distribute products to boxes
问题描述
我有产品和包装盒.我想使用最少的包装盒数进行包装.请忽略产品和包装盒的尺寸(WxHxD).仅关注音量.
I have Products and Boxes. I want to use minimum box count for packaging. Please ignore product and box dimensions (WxHxD). Only focus on volumes.
我需要一种算法来将这些产品放到盒子里.算法必须使用最少的盒子数和可以使用的最小盒子数.算法可以使用同一盒多个.每个产品只能使用一次.
I need an algorithm for placing these products to boxes. Algorithm must use minimum count of boxes and the smallest boxes it can. Algorithm can use same box more than one. Each product can be used only one time.
我尝试过这种算法
- 订购数量按量递增的商品
- 将最小的产品放入最大的盒子中，然后将下一个产品添加到盒子中.直到没有空间可容纳下一个.重复直到产品完成.
根据此算法
- E产品到Z-1盒(可用空间:2900 cm3)
- B产品到Z-1盒(可用空间:2700 cm3)
- F产品到Z-1盒(可用空间:2300 cm3)
- D产品到Z-1盒(可用空间:1700 cm3)
- 用于Z-1盒的产品(可用空间:700立方厘米)
- B产品到Z-2盒(可用空间:1500 cm3)
因此算法使用2个Z Box.但是人脑可以容纳(C + A + F + E)= 3000 cm3(Z框)和(B + D)= 800 cm3(X框)感谢您的所有评论和答复.
So algorithm uses 2 pieces Z Box. But human brain can fit (C+A+F+E)= 3000 cm3 (Z box) and (B+D) = 800 cm3 (X Box) Thanks for all comments and replies.
推荐答案
我将计算使盒子彼此适合的最佳方式.
I would calculate the optimal ways to fit the boxes inside each other.
- 一个Z等于一个V和一个X.
- 一个V等于两个X.
- 一个X等于两个U.
- 1个U等于5个T(对于任何合并的框，必须至少可以将2个框合并为1个框.)
此步骤在计算上可能会相当昂贵，具体取决于您有多少个盒子以及将它们彼此轻松地适配在一起.IE:如果您使用的框大小不是通用倍数，那么这将变得不那么直接和困难.请参阅 https://en.wikipedia.org/wiki/Change-making_problem 真正不错"的例子框大小的组合看起来像(您提供的示例相当不错).
This step may be rather computationally expensive depending on how many boxes you have and how easily you get fit them into each other. IE: This would be much less straightforward and harder if you had box size where they are no common multiples. See the https://en.wikipedia.org/wiki/Change-making_problem for examples of what really "nice" box size combinations would look like (the example you gave is quite nice).
将一个盒子中的所有产品移动到其他盒子中，以尽可能获得接近0的剩余空间为目标，理想的做法是先寻找会导致剩余空间恰好为0的移动(仅将所有内容放入一个盒子中并移动它放到另一个盒子里.
Move all products in one box to other boxes with the goal of get as close to 0 remaining space as you can, ideally start by looking for moves that result in exactly 0 remaining space (only by taking everything in one box and moving it to another box).
然后按照上述规则尽可能多地合并框，只要将框的数量至少减少一个即可.IE: CEF =>V (从技术上讲是 E => F ，然后是 EF => C )， A =>X，DB =>X .然后，您可以从那里进行合并. ADB = V (将 2X 框合并为一个 V 框).
Then merge the boxes as much as you can on the above rules as long as it reduces the # of boxes by at least one. IE: CEF=> V (technically it would be E => F, then EF => C), A => X, DB => X. Then you can combine it from there. ADB = V (Combine 2X boxes into a single V box).
另一个有效的选项是: DF =>X，BCE =>V，A ＝>X .在这种情况下，我们仍然将两个 X 组合为一个 V .也可能有一些解决方案，其中您可能具有 1 V 和 1 Z ，但这仅在您具有 1X 和 1V时才有意义，否则最好使用 2X =>改为1V .
Another valid option is: DF => X, BCE => V, A => X. In this case, we still combine the two X into a V. There are also likely solutions where you might have 1 V and 1 Z, but that only makes sense if you had 1X and 1V, otherwise it would be better to use 2X => 1V instead.
这篇关于将产品分配到盒子的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
