algorithm - 有效的木板切割算法

Question

我需要想出一个算法来切割木板，并尽量减少浪费。切割机直线切割；它不能中途停止，例如转 90° 并继续。

示例：
我有一块尺寸为 280 厘米 x 207 厘米的木板，需要尽量减少切割后的浪费。

我有以下一组表格宽度和长度。

宽度
140
140
140
197
197
30,5
30,5

长度
33
33
33
33
33
33
33

我正在考虑使用“贪婪算法”，因为长度总是相同的。有任何想法吗？

Answer 1

这是二维装箱的一种变体，是 NP 难的。一个常见的近似方法是按宽度对碎片进行分类，然后从仍然足够的最小剩余板上开始切割碎片。在http://cgi.csc.liv.ac.uk/~epa/surveyhtml.html阅读更多关于这个和更复杂算法的信息