Minimizing Waste when cutting pieces

[PhatoseAlpha]

Allright, here's the situation. I have pieces of a raw material, each a fixed length. I have a collection of piece lengths and the amount of each piece I need. A piece or pieces gets cut from a blank, and any leftover that can't fit another piece is waste.

How do I calculate the combinations needed to minimize waste?



Example: My blanks are 144 inches long. I need 14 pieces at 72 inches, 7 at 68, 3 at 30. What do I cut out of each blank?



I fully expect that this has to have been covered before somewhere, since I know bucketloads of industries encounter this sort of problem. I figure there's no need to reinvent the wheel here. Anyone have ideas, or a name for this type of algorithm so I have somewhere to start looking?



Edit: Oh look. Bin Packing Problem. Efficient Optimal, apparently, isn't going to happen. Close to optimal, apparently how close to optimal you're going to get is determined by how much time you're willing to spend.

 

[Markbnj]

Yeah, best fit searches are a long-studied problem in comp. sci. I think the solutions are all O(n). It's kind of similar to the travelling salesperson problem, where you basically end up brute-forcing it, but I haven't exactly kept up with the literature on it.

 

[RocksteadyDotNet]

Cant you make it a algebra equation?

 

[degibson]

The problem you're describing is indeed bin packing. As such, it is NP hard. If you can find a way to optimally solve the problem for all cases, someone will give you a Turing award for sure.

Edit: Bin packing is usually approached with a heuristic, like best fit, first fit, etc. Just look at Wikipedia's bin packing entry.