Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: I'm pretty sure this is a simple problem, but I have no idea whatsoever what to do

  1. #1
    Junior Member
    Join Date
    Jun 2012
    Posts
    2
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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.


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,372
    Thanks
    183
    Thanked 836 Times in 779 Posts
    Blog Entries
    5

    Default 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.
    Last edited by copeg; June 21st, 2012 at 10:06 PM.

  3. #3
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    1,069
    Thanks
    7
    Thanked 215 Times in 191 Posts

    Default Re: I'm pretty sure this is a simple problem, but I have no idea whatsoever what to d

    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.

  4. The Following 2 Users Say Thank You to pbrockway2 For This Useful Post:

    copeg (June 22nd, 2012), Thuzad (June 22nd, 2012)

  5. #4
    Junior Member
    Join Date
    Jun 2012
    Posts
    2
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: I'm pretty sure this is a simple problem, but I have no idea whatsoever what to d

    Quote Originally Posted by pbrockway2 View Post
    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 =)

  6. #5
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    1,069
    Thanks
    7
    Thanked 215 Times in 191 Posts

    Default Re: I'm pretty sure this is a simple problem, but I have no idea whatsoever what to d

    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.

Similar Threads

  1. Replies: 19
    Last Post: March 7th, 2012, 08:26 PM
  2. Pretty basic java program..need some help!
    By LAerving in forum What's Wrong With My Code?
    Replies: 6
    Last Post: January 26th, 2012, 12:09 AM
  3. Help me...its urgent...its simple but no idea
    By zurich91 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: January 24th, 2012, 01:50 PM
  4. Pretty new to Java can someone help with an addObject() problem?
    By alan120184 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: November 1st, 2009, 12:48 PM
  5. help with problem havr no idea what it means
    By mdstrauss in forum Exceptions
    Replies: 4
    Last Post: July 27th, 2009, 01:41 AM