切割材料，求个最优解的算法？

czboyu

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

购买的杆子单根9米长，3.9米／100根，3.65米／38根，3.15米／32根，2.65米／80根，2.15米／80根，问最少购买多少根9米的杆子？、

我想要个最优解？



下面是我手工计算的，不是最优的。

yigo

这个记得应该属于运筹学，把一根原料的所有切割方案列出来，适当选择各切割方案的数量，使得最优。
单根长 根数        单根切割方案                                                                                    根数
3.9    100    x1    2    1    1    1    1    0    0    0    0    0    0    0    0    0    0    0    0    0    0    100
3.65    38    x2    0    1    0    0    0    2    1    1    1    1    0    0    0    0    0    0    0    0    0    38
3.15    32    x3    0    0    1    0    0    0    1    0    0    0    2    2    1    1    1    0    0    0    0    32
2.65    80    x4    0    0    0    1    0    0    0    2    1    0    1    0    2    1    0    3    2    1    0    80
2.15    80    x5    0    0    0    1    2    0    1    0    1    2    0    1    0    1    2    0    1    2    4    81
                    7.8  7.55 7.05 8.7  8.2  7.3  8.95 8.95 8.45 7.95 8.95 8.45 8.45 7.95 7.45 7.95 7.45 6.95 8.6   
              y    23    0    0    54   0    0    27   11   0    0    2    0    1    0    0    0    0    0    0    118
算出来是118根