求如何切割浪费最少

czboyu

单根长度        9        米                共需购买                根
                                               
切割长度        3.9        米        100        根               
切割长度        3.65        米        38        根               
切割长度        3.15        米        32        根               
切割长度        2.65        米        80        根               
切割长度        2.15        米        80        根               


原料的长度9米，需求的长度和数量确认，求如何切割浪费最少


补充内容 (2023-5-28 12:02):
购买的杆子单根9米长，3.9米／100根，3.65米／38根，3.15米／32根，2.65米／80根，2.15米／80根，问最少购买多少根9米的杆子？、

我想要个最优解

王守恩

120根，其中
30根=180-78-73
70根=180-78-53-43
08根=180-73-63-43
12根=180-63-63-53

nyy

果然是钢管切割问题！
先穷举出所有模式。
然后再用lingo！

aimisiyou

王守恩 发表于 2023-5-27 18:52
120根，其中
30根=180-78-73
70根=180-78-53-43

119根。

czboyu

aimisiyou 发表于 2023-5-28 07:31
119根。

可以把EXCEL文件发一下吗？我要最佳算法

czboyu

我要最佳的算法，谢谢大家

aimisiyou

czboyu 发表于 2023-5-28 09:31
我要最佳的算法，谢谢大家

没有最佳算法，除非暴力枚举，但时间复杂度是不可接受的。

nyy

aimisiyou 发表于 2023-5-28 09:57
没有最佳算法，除非暴力枚举，但时间复杂度是不可接受的。

这就是个最优化问题呀，谁说没最有解的？？

aimisiyou

nyy 发表于 2023-5-28 10:27
这就是个最优化问题呀，谁说没最有解的？？

我说没有最优解了吗？所谓的最佳算法是确保能得到最优解的算法，那只有暴力算法。

czboyu

aimisiyou 发表于 2023-5-28 10:34
我说没有最优解了吗？所谓的最佳算法是确保能得到最优解的算法，那只有暴力算法。

可以暴力，关键是算法