php - 下料问题

Question

我正在尝试以最少的掉落或浪费来嵌套 Material 。

Table A

Qty Type Description Length

2   W    16x19       16'
3   W    16x19       12'
5   W    16x19       5'
2   W    5x9         3'


Table B

Type Description StockLength

W    16X19       20'
W    16X19       25'
W    16X19       40'
W    5X9         20'

我全面研究了贪婪算法、装箱算法、背包算法、一维 CSP、分支定界算法、蛮力算法等。我很确定这是一个下料问题。我只需要帮助想出运行它的功能。我不仅有一个库存长度，还有多个库存长度，用户可以输入他自己的不太常见长度的库存。如果您能帮助计算在 PHP 中使用的函数或算法，以得出优化的切割模式和所需的库存长度，并且浪费最少，我们将不胜感激。

谢谢

Answer 1

如果您的问题是“给我代码”，恐怕您没有提供足够的信息来实现一个好的解决方案。如果您阅读了整个答案，就会明白原因。

如果您的问题是“给我算法”，恐怕您在错误的地方寻找答案。这是一个面向技术的站点，而不是面向算法的站点。即使我们程序员当然理解算法(例如，为什么在循环的每次迭代中将相同的字符串传递给 strlen 是低效的，或者为什么冒泡排序除了非常短的列表之外还不行) ，这里的大多数问题就像“我如何使用语言/框架 Y 来使用 API X？”。

回答像这样的复杂算法问题需要一定的专业知识(包括但不限于大量的数学能力)。领域人operations research解决此类问题的次数比我们大多数人都多。这是一个 introductory book关于这个话题。

作为一名试图为现实世界的问题寻找实用解决方案的工程师，我首先会得到这些问题的答案:

• 您尝试解决的平均问题实例有多大？由于您的一般问题是 NP 完全问题(正如 Jitamaro 已经说过的)，中等大的问题实例需要使用启发式方法.如果你只打算解决小问题实例，你可能能够实现一个找到精确最优的算法，但当然你必须警告你的用户他们不应该使用你的软件来解决大问题实例.

• 是否有任何模式可以用来降低问题的复杂性？例如，元素是否总是或几乎总是有特定的尺寸或数量？如果是这样，您可以实现一种专注于为常见场景生成高质量解决方案的贪心算法。

• 您的最优性和计算效率权衡是什么？如果您只需要一个好的答案，那么您不应该浪费精力或计算努力来尝试提供最佳答案。信息，无论是由人提供还是由计算机提供，只有在需要时可用时才有用。

• 您的客户愿意为高质量的解决方案支付多少费用？与数据库或 Web 编程不同，后者几乎每个人都可以完成，因为算法被保持在最低限度(例如，你很少编写 SQL 数据库提供查询结果的确切过程)，运筹学确实需要数学和工程技能。如果您不对它们收费，那么您就是在赔钱。