2 Replies - 430 Views - Last Post: 19 July 2012 - 09:48 PM

#1 SpiderSpartan  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 14
  • View blog
  • Posts: 120
  • Joined: 06-February 08

Algorithm for most efficient use of 2x4s

Posted 19 July 2012 - 12:30 PM

I've been doing a lot of building around the house lately using 2x4s to make shelves and work benches. These projects haven't been big so I've manually gone through and organized the cut pieces I've needed into the most efficient layout to were I can buy the least amount of 2x4s needed for the project. The more I build these little 2x4 frames though the more I think wouldn't it be nice if there was a calculator I could use to quickly do this for me. I've done some googling and there are calculators for framing walls, but not for random structures (that I can find anyways).

So I'm looking for thoughts on an algorithm for sorting a list of smaller pieces of wood into a standard sized piece. My first and simplest thought is to take the largest number that doesn't put you over the standard size and add it together until the remainder of the standard size is less than any one piece. For instance, if you need 2 x 62", 2 x 24", and 4 x 21" pieces and your using a standard 96" (8') board, you would end up with 2 x (62+24) leaving a remaining 10" of waste on 2 boards and another 1 x (4 x 21") leaving 12" of waste.

This algorithm seems to work for my current project, but it feels like there would be situations where it may not produce the best results. Some situation where it may be better to fill in 3 x 21" boards instead of 2 x 24" or something of the sorts. Anyone have any experience or suggestions on something like this? Thanks.

Is This A Good Question/Topic? 1
  • +

Replies To: Algorithm for most efficient use of 2x4s

#2 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon

Reputation: 9513
  • View blog
  • Posts: 16,467
  • Joined: 19-March 11

Re: Algorithm for most efficient use of 2x4s

Posted 19 July 2012 - 01:48 PM

If I'm not mistaken, this is analogous to the knapsack problem, or the scheduling problem. Fortunately, for most home projects the numbers will be relatively small, so brute force isn't too painful. Probably the only case where brute force and a 2X4 don't add up to "extremely painful".
Was This Post Helpful? 1
  • +
  • -

#3 Choscura  Icon User is offline

  • D.I.C Lover

Reputation: 469
  • View blog
  • Posts: 2,230
  • Joined: 18-October 08

Re: Algorithm for most efficient use of 2x4s

Posted 19 July 2012 - 09:48 PM

Off the top of my head, a place to start might be shuffling/trading places between the pieces when any two single pieces of scrap are longer than any one single piece to be used, with some basic logical direction to make for efficient trading.

If you want to have the program suggest sizes, that's another ballgame, but doable if done cleverly. I think the Mythbusters guys have a book that specifies the standard dimensions of some objects- how high a chair seat should be, how wide, how deep, etc- and that kind of fixed value could be fed into a program to figure out the optimum sizes for the other variable dimensions, for example.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1