My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum

Thanks Tree1Thanks
  • 1 Post By mathman
LinkBack Thread Tools Display Modes
August 24th, 2017, 06:05 AM   #1
Joined: Aug 2017
From: UK

Posts: 2
Thanks: 0

Wood cutting problem


New to this forum, so sorry if I am not posting in the right place.

I have a problem; I need to cut a number of pieces of wood to certain lengths (the width and depth are standard and not relevant here). I know the number and lengths of all the lengths I need, but I can only buy the wood in boards of 2400mm or 1800mm. What I would like to do is find the number of boards of each length that I need to buy, and how to cut them in the most efficient way.

I would like to write a function to do this am competent at coding but do not know how the logic of the function should work. I'd also like to try and generalize the function to work for any input sizes and quantities and any given board that can be purchased.

Here's my example:

I want to create the following board quantities and lengths:

8 x 2060mm
14 x 450mm
2 x 458mm
4 x 283mm
2 x 197mm
2 x 486mm

I can only purchase 2400mm or 1800mm length boards, from which I must cut the above lengths.

My only thought so far is to first arrange the boards into every possible combination, then line each order up against the 2400mm and 1800mm boards to see which uses least/produces least waste. There are 32 boards so I believe this gives me 32! positions that they could be in. This is obviously too large to do anything with. Clearly there are a lot of positions that I don't care about, for example it doesn't matter which of the 14 boards that are 450mm is at a given position in the order. It doesn't matter about orders that are the reverse of another order etc.

This way seems very inefficient and at the end still wouldn't identify any solutions that are more efficient by using only the shorter boards to cut from etc.

Looking for any help you can give me to get my head around this problem.

If anyone wants to get really crazy then there is a per meter price difference

14.78 GBP for 2400 making 6.16 GBP/meter
11.82 GBP for 1800 making 6.57 GBP/meter

It would be great to figure out the function that gives the most efficient option in terms of price also.

If I'm totally in the wrong place please feel free to point my in the right direction.

Thanks in advance.


Last edited by skipjack; August 24th, 2017 at 10:45 AM.
droobilicious is offline  
August 24th, 2017, 10:50 AM   #2
Global Moderator
Joined: Dec 2006

Posts: 20,635
Thanks: 2080

This isn't easy.
skipjack is offline  
August 24th, 2017, 12:31 PM   #3
Joined: Aug 2017
From: UK

Posts: 2
Thanks: 0

Haha, Very true my friend. That is why I am here to bow to people way more knowledgeable than me

I will probably end up just using some guess work to create these cuts in practice but as a bit a purist I am very much interested in what the maths behind an "ideal" solution would be because I have seen other applications for this maths. I could be wrong because I am in no way a mathematician but i think the problem boils down to a "bucket sort" function. I am also interested in the base problem of how you list all permutations that the cuts could be sorted into (the 32!) and then how you mathematically rule out the logically similar sorts (where the sort puts 2 different cuts of the same measurements in the same place, or the order is the exact reverse of another iteration etc).

Thanks for reading anyway.

droobilicious is offline  
August 24th, 2017, 01:24 PM   #4
Global Moderator
Joined: May 2007

Posts: 6,759
Thanks: 696

Start with the obvious. To get 8x2060, you need 8x2400. The remnants can the be used for 4x283 and 2x197. This leaves you 3 sizes to handle.
Thanks from greg1313
mathman is offline  
August 24th, 2017, 03:45 PM   #5
Math Team
Joined: Oct 2011
From: Ottawa Ontario, Canada

Posts: 14,415
Thanks: 1025

To "experiment" coding-wise, perhaps you could use
simpler lengths; as example, purchase boards of
150 and 100 in length, then cut into needed boards
of 120, 60 and 30.
Once you "see" what's involved, then apply same
routine to larger boards....
Denis is offline  

  My Math Forum > High School Math Forum > Algebra

cutting, problem, wood

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Cutting off decimals benmuskler Number Theory 6 January 6th, 2013 01:04 PM
cutting sticks problem jeepin81 Algebra 0 April 15th, 2011 01:17 PM
Cutting problem monicao Applied Math 1 November 27th, 2009 10:31 AM

Copyright © 2019 My Math Forum. All rights reserved.