Possibility Program for number of pieces

Question

I would like to put a program together to calculate the number of 60' pieces would be needed from a list of shorter pieces. For example, I sell rebar cut to length from our standard length of 60'-0". Now the length the customer requires are as follows:

343 pc @ 12.5'
35 pc @ 13'
10 pc @ 15'
63 pc @ 15.5'.......

There are 56 total lengths ranging from 12.5' to 30.58'

The idea is to limit the amount of waste from the 60' piece. The input from the user would be:

• number of differnt lengths
• Length of piece to cut from
• count of different lengths

The result would be the number of prime pieces needed to fulfill the order.

What well-known algorithms exist that could help me solve this problem?

Answer 1

This is very much like the bin packing problem. There are a number of heuristics that will give you an answer that is not optimal but might be good enough for your purposes.

Essentially you are looking to optimize an objective function that gives you the least amount of waste, to solve exactly you may want to look into linear programming and the simplex algorithm.

There's some packages out there already that could help with this. Perhaps have a look at http://www.coin-or.org/

Answer 2

This appears to be a variant of the Knapsack Problem - there's already a similar question here on Programmers.