Thread: 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.

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.

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/9n+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 =)

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.