Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
Is there a question you would like to ask? If it's "Can you write this program for me?", I doubt anyone here will. –  Bernard Nov 29 '11 at 14:51
add comment

2 Answers 2

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/

share|improve this answer
1  
This seems like a perfect example of dynamic programming to me. –  Jetti Nov 29 '11 at 17:46
add comment

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

share|improve this answer
3  
It is closer to the bin packing problem –  Sign Nov 29 '11 at 15:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.