# Minimum cost of wood for woodworking project problem

This is a fun one, I really can't wrap my head around it. It's like an n-sum problem combined w/ a knapsack problem and I cant seem to find a solution.

I'm currently building a cabinet, and had just enough wood that if I calculated my cuts right, I would've had enough, if I had even cut one certain length from one board instead of another, Id have needed an extra length of wood and would have to go back to the store. And it made me start thinking about if there is a non brute force solution for calculating the minimum amount of wood lengths I needed.

Then started to think about it further, given a bin of infinite lengths of wood in various lengths. Ie: infinite 96", infinite 72", etc, and a cost for each. What would be the minimum cost of wood I'd need to buy.

So the problem would be like, given lengths of wood that have a certain price:

{ cost: 3, length: 96 },
{ cost: 2, length: 72 },
{ cost: 4, length: 144}


And a list of cuts (lengths) needed,

[ 24, 24, 24, 24, 48, 48, 48, 48, 36, 36, 36, 36 ]


What would be the cheapest combination of wood pieces I could buy and still have enough wood. (Lets assume that we do not have to take into account the amount of wood lost during a cut due to the width of the blade)

• What would you like to know about this problem? It is at least as hard as the knapsack problem, so it is obviously NP-hard, thus you should not expect any algorithm that is both always efficient and always produces the correct answer. – D.W. Oct 19 '20 at 6:44
• (bin of infinite lengths of wood in various lengths looks screwed up - infinite number of boards, each with a length in a smallish set? Sounds everyone's favourite hardware store.) The example looks way to simple: 6×72. – greybeard Oct 19 '20 at 10:21