切割库存问题

Question

我试图用最少的水滴或浪费来筑巢材料.

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'

我一直在寻找贪心算法,Bin装箱,背包,1D-CSP,分支机构,蛮力等等.我很确定这是一个切割库存问题.我只是需要帮助来提供运行它的功能.我不只是有一个库存长度而是多个,并且用户可以输入他自己的不常见长度的库存.任何帮助计算在PHP中使用的函数或算法来提出最少的浪费所需的优化切割模式和库存长度将非常感激.

谢谢

Answer 1

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