One dimensional cutting algorithm with minimum waste
- by jm666
Can anybody point me to some resources about "cutting algorithm"?
The problem:
have rods with length of L meters, e.g. 6 m
need cut smaller pieces of different lengths, e.g. need:
4 x 1.2m
8 x 0,9m
etc... (many other lengths and counts)
How to determine the optimal cutting, what will produce the minimum wasted material? I'm capable write an perl program, but haven't any idea about the algorithm. (if here is already some CPAN module what can help, would be nice).
Alternatively, if someone can point me to some "spreadsheet" solution, or to anything what helps.
Ps: in addition, need care about the "cutting line width" too, whats means than from the 6m long rod is impossible to cut 6 x 1m, because the cutting itself takes "3mm" width, so it is possible cut only 5 x 1m and the last piece will be only 98.5 cm (1m minus 5 x 3mm cut-width) ;(.
