Cable Lengths Algo

1 pointyannis2 comments

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?

View on HN

Feels 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

Thanks, it is very similar actually, I followed the link and is the cutting stock problem http://en.wikipedia.org/wiki/Cutting_stock_problem, seems quite complex. Need to do more reading!

Reply on news.ycombinator.com