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&quot;, infinite 72&quot;, 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)
As D.W. rightly pointed out, it is a generalisation of the knapsack problem. Its closest relative is probably the cutting stock problem, where the goal is to minimise waste.
The cutting stock problem is typically solved using a (quite natural!) translation to integer linear programming. That seems like the best bet for your problem, too.