2
$\begingroup$

I'm trying to come up with an algorithm for optimizing cutting a rod. Most of the examples I see online are for a stock of rod of a single length and optimizing the way to cut it up for max price.

I need something where the user enters length cuts they want (e.g. 2 of 1" length, 5 of 6" length, 10 of 8" length) and then they can choose to have this optimized for multiple stock rod lengths where they can choose which stock lengths they want to use, either 1 or multiple lengths, (e.g 8' stock, 10' stock, 12' stock).

I don't have a computer science background, so am not as familiar with algorithms and whatnot. From looking around I've seen Greedy Algorithm recommended, but was a little confused, because most examples were more simple.

I can logically come up with some really poor optimization starategy like 1.) see if any stock lengths are completely divisible by any of the desired cut lengths and do those first 2.) see if any stock lengths are completely divisible by any combination of desired cut lengths and do those next 3.) from there just kind of pick a pattern and stick to it like use up the smallest cuts first and largest last.

Possibly after doing a problem like this, I may need to move on to optimizing rectangular cut areas from a piece of plywood, but I can't even figure this out yet. Any help to point me in the right direction would be appreciated. I am a mobile app developer, so I'm trying to code this for a carpentry app.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ Can you state your optimization problem in full? At present it's not clear what you're trying to optimize. Clearly state the input, what the potential outputs are, and how do you measure how good an output is (i.e., what function you are trying to optimize over). $\endgroup$ – Yuval Filmus Nov 20 '17 at 19:31
  • $\begingroup$ As an example, a store sells rods in stock lengths of 8', 10', and 12'. The user needs cuts of (Qty. , Length): (5, 1"), (10, 5"), (7, 8"). How many of each size stock should be bought to have the least amount of excess wood. So, for instance, an answer would be to buy stock (Qty. , Length): (2, 8') (1, 10') (0, 12'). That is not a real answer to this problem, but the format of the answer needed. $\endgroup$ – Michael Nov 21 '17 at 1:41
  • $\begingroup$ Please don't put information in the comments. Instead, edit the question to incorporate all information into the question, and so it reads well for someone who encounters the question for the first time. People shouldn't need to read the comments to understand what you are asking. $\endgroup$ – D.W. Nov 21 '17 at 23:42
  • $\begingroup$ Have you tried dynamic programming? cs.stackexchange.com/tags/dynamic-programming/info I don't understand the question fully so I'm not sure whether there will be an efficient dynamic programming algorithm, but it smells like the sort of thing that might be solvable with dynamic programming. $\endgroup$ – D.W. Nov 21 '17 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.