关于工业生产中的一个算法问题

[catshen]

51 假期回老家，发现家纺行业切割材料的问题，我看了下本质是一个算法问题：

• 有一个大矩形区域，矩形区域的尺寸规格为：2*N
• 有若干矩形，尺寸规格不等，注：这些小矩形尺寸规格 a*b，a 和 b 中的有一个值必定在 2 以内
• 现在将这些小矩形填充到大矩形区域，使得耗用的大矩形区域的面积最少

求解图形化规划方案 即输入若干尺寸小矩形规格，输出规划图形，工人可以根据规划图形划料

目前都是人工排版划料，效率有提升空间～

如能解决，现金感谢～

https://codeincomplete.com/articles/bin-packing/ 这个似乎比较不错

[wtof]

二维装箱问题？记得是个 NP 问题来着，量不大 DLX 搞一下应该也可以吧

[murmur]

这得看你什么样的布了，如果是单色或者是重复花纹还好，如果是复杂印花，有的部分必须浪费因为要显示整个一套图案

[catshen]

@murmur 纯色的，所以好弄一些

[catshen]

@wtof https://blog.csdn.net/code_long/article/details/81182516 应该就是这个吧

[ccpp132]

虽然 2 维，这个问题的限制倒是比较好搞。把 1xn 的先挑出来。剩下 2xn 的只有一种放法，1xn 的就分两行，尽量相等，相当于一个装一半总大小的 1 维装箱。唯一一个例外是可能多一个 1x2 的旋转一下更好

[CrazyMoon]

造船行业里已经有现成的解决方案了，偶们厂里把这个叫套料，一般是软件自动生成图形，人工辅助。具体算法不清楚。

[CrazyMoon]

楼主可以查查论文试试

[catshen]

@CrazyMoon 谢谢，看来要废不少脑子了