4 ms·
Cable Lengths Algo
I need an algo to do the following:
(01) You have a number of cable drums of length L each.
(02) You need to cut lengths of cables from these drums say, n1xL1,n2xL2,n3xL3, where n is the number of cables and L is their length.
(03) You need to minimize waste.
Does anyone one of a solution? Any mathematics papers?
- RiderOfGiraffes 17y agoFeels a lot like a variation on the Knapsack problem, which is known to be NPC-Complete. If that's true (and I haven't verified it - that's your problem) then you can use any of the variations on the greedy algorithm to get a reasonably good solution. http://en.wikipedia.org/wiki/Knapsack_problem http://en.wikipedia.org/wiki/Knapsack_problem
- yannis 17y agoThanks, it is very similar actually, I followed the link and is the cutting stock problem http://en.wikipedia.org/wiki/Cutting_stock_problem http://en.wikipedia.org/wiki/Cutting_stock_problem, seems quite complex. Need to do more reading!