7

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

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'

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

谢谢

4

2 回答 2

4

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

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

回答这样的复杂算法问题需要一定的专业知识（包括但不限于大量的数学能力）。运筹学领域的人在这类问题上的工作比我们大多数人都多。这是一本关于该主题的介绍性书籍。

作为一名试图找到实际问题的实用解决方案的工程师，我首先会得到以下问题的答案：

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

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

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

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

于 2011-07-14T17:19:47.377 回答
2

在我看来，这就像一维装箱的变体。你可以尝试一个最合适的，然后用不同的表格排序来尝试。无论如何，在 3/2 的最优值中不存在解决方案，因为这是一个 NP 完全问题。这是一个很好的教程： http: //m.developerfusion.com/article/5540/bin-packing。我用了很多来解决我的问题。

于 2011-07-14T00:53:00.927 回答