0
$\begingroup$

Given a length N (e.g. 20) and an array of lengths which are all <= N (e.g. [15, 1, 6]) I'd like an algorithm that finds the minimum number of N lengths necessary to be cut into the array of lengths.

The practical application here is for ordering steel: given a design from an engineer I'd like to specify how many lengths of steel need to be ordered to build the design.

For the example above, the desired result is 2, since you could cut a single 20 foot length into 15 and 1 (leaving scrap of 4 feet), and a second 20 foot stick needed to cut into the 6 foot length with a 14 foot scrap. Notice how larger scraps are preferred.

Improve this question
$\endgroup$
4
  • $\begingroup$ This looks very much like bin packing. $\endgroup$
    – gnasher729
    Nov 16 at 19:48
  • $\begingroup$ Just looked it up, yeah it seems to be the same problem just reworded. Looks like it's NP complete, which is a bummer though. Thanks for the tip $\endgroup$
    – ajHurliman
    Nov 16 at 22:48
  • $\begingroup$ Due to specifics, the Cutting stock problem has been considered. $\endgroup$
    – greybeard
    Nov 17 at 6:42
  • $\begingroup$ In this case, don’t be afraid of NP complete. Getting the optimal solution is nice, but often almost optimal is good enough. And if your total length is say 383ft, then you know 19 times 20ft cannot be enough, but with 20 times 20ft you have 17ft leftover so it’s likely to be easy to get a solution with 20 items. On the other hand, if you need a total length of 399ft then it may be easy to show that 20 items, wasting only 1ft, is impossible. And of course for small numbers of items NP complete can still be solvable. Bin packing tends to be easier to solve than some other problems. $\endgroup$
    – gnasher729
    Nov 17 at 22:45

0

Reset to default

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.

Browse other questions tagged or ask your own question.