分配碎片时使用什么算法？
嗨，我在一家制造公司工作，该公司的运营方式就是这样的
我们得到一卷特定尺寸的材料，我们的供应商假设每卷8000米。然后我们收到了不同客户的订单，较小的尺寸，如2000米，3000米等。我想知道我应该如何去创建一个软件，在其中他们只需输入他们当前的辊尺寸和我们目前拥有的不同订单，它可以生成最好的方法来切割不同的辊，以最大限度地减少浪费。
例如，在某个特定的时间点，我们可能会收到以下订单:2件3000米，2件4000米，6件1500米
然后我们需要输入的就是上面的订单以及供应商提供给我们的卷筒尺寸，在这个例子中，我们假设它是8000米。
然后，软件应该生成输出，如第一卷-两个4000米的卷浪费0个3000米的卷2个-Two块和1个1500 (卷浪费500)卷3-5个15000 (卷浪费500)
脚本应该是优化的，因为上面的例子很小。通常我们一次会收到大约200件的订单。
我正在考虑用PHP和MYSQL做这件事，这样它就可以是基于web的，公司周围的人也可以使用它。
我知道我们可以通过暴力尝试每种组合来做到这一点。但是，在这种情况下，是否有其他排序算法和技术可以帮助解决此问题呢？
回答 2
Stack Overflow用户
发布于 2012-04-29 03:08:55
这是广为人知的cutting stock problem，您希望在完成所有订单后将浪费降至最低。
以下是维基百科对它的描述：
下料问题是一个最优化问题，或者更具体地说，是一个整数线性规划问题。它产生于工业中的许多应用。想象一下，您在造纸厂工作，有许多固定宽度的纸卷等待切割，但不同的客户想要不同数量的不同宽度的纸卷。你将如何削减卷，以使浪费最小化(剩余量)？
一般情况下是NP-hard的，这意味着没有快速算法来产生最优结果。
但是，您可以编写一种算法，生成计算速度快且“相当”好的近似解。
编辑(courtesy @David)：
如果您从制造商那里得到的原始轧辊总是相同的尺寸，在本例中为8,000米，那么下料问题就简化为1D bin packing problem，它更容易解决(但仍然是NP困难的)。
正如@David在他删除的答案中提出的那样，贪婪的解决方案是一种快速且廉价的近似解决方案。
编辑2：
我说错了一点。对于装箱问题，目前还没有已知的多项式时间近似方案。The greedy algorithm is actually pretty alright, though.
Stack Overflow用户
发布于 2012-04-29 03:06:55
您正在寻找一种1d装箱算法。有许多策略可以解决这个问题- First-Fit，Best-Fit，Random-Fit。我在phpclasses.org上写了一个php解决方案。你可以免费下载我的程序(打包)。事实上，我已经为此赢得了一个奖。如果你的问题不是很严重，我会尝试使用暴力方法。
https://stackoverflow.com/questions/10366611
复制相似问题
腾讯云开发者
