1
$\begingroup$

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)

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Oct 19, 2020 at 6:44
  • $\begingroup$ (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. $\endgroup$
    – greybeard
    Oct 19, 2020 at 10:21

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.