问切削杆的变化(动态规划)
EN

Stack Overflow用户

提问于 2015-08-26 18:23:37

回答 1查看 958关注 0票数 1

最近我听到了一个问题，那就是切割杆问题的变化。

如果您的杆长为10，并且从客户那里得到不同尺寸棒的订单(即一个客户订购的杆长为4，另一个杆长为7，另一个杆长为6)，那么您需要多少棒才能最大限度地减少损失？

一段时间以来，我一直试图想出一个解决方案，但我想不出一个令人信服的解决方案。

谢谢!

编辑：

您将得到所有订单的数组。例如，4,8,9,1,4,3,7.棒子的长度为10 (因此每个订单必须小于10)。

发布于 2015-08-27 10:40:42

除非我忽略了问题中“最小化损失”的一些细节，否则这个问题似乎与装箱问题一样，这是NP难的。

似乎有一些动态规划的解决方案，似乎比蛮力更快，但仍然不太令人印象深刻。从维基百科上可以看到，有一些快速、准确的算法可用(当然，不是多项式)。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/32233999

复制

相似问题

问切削杆的变化(动态规划)EN