2D装箱算法
Col*_*lin 8 javascript algorithm bin-packing node.js
我花了一些时间研究二维装箱算法。我在算法方面没有丰富的经验，尤其是在高级数学方面，但我可以编码:)
这里展示了我需要实现的完美示例：http://www.cutlistoptimizer.com。它有效，但我不知道它使用什么算法。
我尝试了很多方法，其中一些非常简单，例如https://codeincomplete.com/posts/bin-packing/ DEMO 这里，但它不支持旋转，这是必不可少的。
对我来说最有前途的是https://ssbothwell.github.io/greedypacker-react/ 不确定我做错了什么，但它并没有计算出最适合我的。我尝试了不同算法的不同组合。
演示数据：纸张尺寸：宽：2655，高：2100
{ w: 900, h: 320 },
{ w: 320, h: 900 },
{ w: 900, h: 320 },
{ w: 900, h: 320 },
{ w: 900, h: 320 },
{ w: 900, h: 320 },
{ w: 900, h: 320 },
{ w: 900, h: 320 },
{ w: 900, h: 320 },
{ w: 386, h: 310},
{ w: 386, h: 310},
{ w: 386, h: 310},
{ w: 386, h: 310},
{ w: 386, h: 310},
{ w: 860, h: 320},
{ w: 860, h: 320},
{ w: 564, h: 310 },
{ w: 452, h: 293},
{ w: 720, h: 530},
{ w: 720, h: 530},
{ w: 696, h: 530},
{ w: 696, h: 100 }
这些部件应装在一张纸内。
参考图片
经过一段时间的研究，我发现我可能应该使用遗传算法来发展这些启发式方法。这有意义吗？
小智 0
您可以在文献中找到这个问题，称为 2KP，即二维背包问题。在您的具体情况下，这是没有方向约束的 2KP（即对象可以旋转）。
遗憾的是，这个问题属于 NP-Hard 问题类别，这意味着不存在已知的多项式时间解。
根据您的用例，训练遗传算法可能是一个很好的解决方案，可能与其他研究的启发式方法混合在一起。一些常见的启发法包括：从左下角向外填充、找到最大的开放空间并用最适合的部分填充、按级别排序等。由于您也在考虑对象的旋转，因此逻辑启发法限制了可能的旋转（例如，只有 45 度的台阶）。
两篇相关论文：
矩形块二维背包问题的遗传算法。安德烈亚斯·博特菲尔德，托比亚斯·温特