I'm pretty sure this is a simple problem, but I have no idea whatsoever what to do
I'm fairly sure this is not a complicated problem. I'm working as a handyman this summer for some extra cash and currently I'm cutting curtain rails, yes really, and I figured I could write a little program to help out with this issue I'm having which is basically an optimization problem.
I get a bunch of 600 cm long curtain rails that I cut into smaller rails usually about 150-400 cm in length. Usually I have a list of about 15-40 rails that need to be cut. I can usually squeeze in two-three rails and on rare occasions four and whatever is left of the rail I throw away. I was wondering how do I write a program that simply outputs the optimal distribution of these 15-40 measurements into the least amount of 600 cm rails because sometimes the pieces I have to throw away are a meter plus in length.
Kinda reminds me of a linear programming problem, but like I said my brain just isn't working at the moment. I can't even think of a way to brute force it which makes me feel kinda sad and stupid right now.
Anyone got any ideas? Train of thoughts, educational examples, pseudo code, all help is appreciated.
Re: I'm pretty sure this is a simple problem, but I have no idea whatsoever what to d
Sounds like it could be framed as a linear programming problem (minimize the amount of material thrown away). Perhaps limit the length of each rail, and bound the number of each size based upon your input list. I'd suggest to try and break the problem down a bit further and post a more formal mathematical definition. For instance, if you consider the LP problem as a matrix of rows and columns, the rows could be the rail size (fixed), the columns the number of each size you need to cut from each rail plus an error factor in each which you then try and minimize. The Apache commons math lib has a simplex solver you can use if you can formulate the problem into an LP problem.
Re: I'm pretty sure this is a simple problem, but I have no idea whatsoever what to d
Quote:
I'm cutting curtain rails
Cut the rails longest first, from the first suitable source. Not guaranteed optimal, but near enough and takes little thought.
Or is it a programming question? In that case see, eg, Bin packing in Wikipedia. Unflatteringly, that article describes the method given above (which it calls first fit decreasing) as the simpler of the two simplest methods. Apparently someone proved in 2010 that it would use no more than 11/9n+6/9 rails where n is the "real" answer you are trying to find.
Re: I'm pretty sure this is a simple problem, but I have no idea whatsoever what to d
Quote:
Originally Posted by
pbrockway2
Cut the rails longest first, from the first suitable source. Not guaranteed optimal, but near enough and takes little thought.
Or is it a programming question? In that case see, eg,
Bin packing in Wikipedia. Unflatteringly, that article describes the method given above (which it calls
first fit decreasing) as the simpler of the two simplest methods. Apparently someone proved in 2010 that it would use no more than 11/9
n+6/9 rails where
n is the "real" answer you are trying to find.
Hi, the bin packaging problem seems to be exactly what I'm looking for. I'll get cracking on figuring out how to implement a solution, however I'm wondering why you say simply going largest to smallest would yield a near enough optimal solution? Thanks for the help too =)
Re: I'm pretty sure this is a simple problem, but I have no idea whatsoever what to d
Quote:
I'm wondering why you say simply going largest to smallest would yield a near enough optimal solution?
It's just that's the way I have done such things. The plan is to get the longer rails "out of the way" by cutting them first, then cutting the smaller rails from the remaining pieces. That reasoning is simply iterated as both the remaining source pieces and the pieces you want to cut get smaller.
