我被要求为我的学校开发一个用于制造环境的简单软件。
这是场景：
我得到了一个尺寸列表 - 每个尺寸都反映了一块木板，例如，我有一块 24" x 30" 的木板、30" x 30"、30" x 48" 等等。这些板是他们切割原材料的过程的副产品。
原材料采用两种不同类型的板尺寸 60" x 120" 和 48" x 96"。
他们想知道从原材料中切割板材的最佳方式——“最佳”方式被定义为原材料和残留物最少的方式。他们还想知道将使用的原材料数量，例如 30 块 60 英寸 x 120 英寸的板和 3 块 48 英寸 x 96 英寸的板。
他们能够水平或垂直切割任何板，这意味着 24" x 30" 可以切割成 24" x 30" 或 30" x 24"。
如果给我总共 50 个板（可能是相同尺寸），我可以有 2^50 种不同的组合 - 这对我来说似乎太长了，因为他们将在数千个不同尺寸的板上运行软件。
我想知道是否有人知道可能适合这种情况的算法。
谢谢！
用于矩形二维切割和包装问题的经典简单算法是Wang 算法
然而，纯王的算法能够产生最佳的断头台切割模式，即所有切割从剩余材料的一个边缘一直移动到相对边缘的模式。它不能产生如下一种非断头台图案
+---------+---+
| | |
+---+-----+ |
| | | |
| | | |
| +-----+---+
| | |
+---+---------+
然而，对于许多应用来说，断头台切割模式被认为是足够好的。因此，您可能需要考虑该算法（因为它非常简单）。
还有基于模拟退火技术的近似随机算法（详细描述可以在VLSI 设计的模拟退火一书中找到（在网上找不到），它们能够产生非断头台图案。
在任何情况下，为此类问题找到精确的解决方案通常需要大量的计算来生成和分析各种可能的变体，这在大多数情况下是不切实际的。大多数时候，人们更喜欢坚持使用好的近似/启发式算法，这些算法工作得更快。Wang 的算法可以使用启发式过滤器的数量进行定制，从而加快搜索速度（冒着丢失最佳解决方案并将其替换为“几乎”最佳解决方案的风险）。