The classical "partition problem" asks how many ways one can write a given natural number as a sum of smaller numbers. One variant of this would be to ask if a positive real number can be expressed as a sum of given smaller but positive real numbers.
I am interested in a similar problem that comes up in carpentry.
Say I want to cut a sheet of wood into several smaller pieces of wood. I know the geometry of the smaller pieces of wood I would like to cut my large sheet of wood into. Both the input and desired output (to keep things reasonable) are all rectangular. How do you decide if it is possible to make the cuts?
To add a little realism to the question, what if we further posit that the cutting operation is a strict "loss" operation, and a certain amount of the material is lost along the cut -- this is the width of the saw/cutting blade. You also know (ahead of time) the geometry of the wood you start with. Perhaps there's more than one sheet you start with. Frequently one buys sheets of wood with near identical geometry at wood shops. So one's input in this question is a rectangular wood type with a particular geometry (length and width), and a desired output of a list of boards with their own particular lengths and widths. We want to know the minimal number of input boards to buy, and how to cut them.
I know how to answer this question for any given input parameters. It tends to be a rather exhaustive process, like the classical partition problem but far more time consuming as there is more choice.
Has anyone written software that does the work for you, and gives you some cutting diagrams for such "perfect" ways to cut wood?
Given all the lovely smart CNC machines out in the world, I imagine there are some nice smart algorithms available. But I don't know where to look.
I'm asking this question because I'm about to invest in some wood to make some furniture, and I'd like to certify I'm wasting as little wood as possible.