Optimal way to cut boards to given length

From wikiluntti

Introduction

Problem: Need to cut 6×110 cm similar pieces from 4×200 cm wood. The parts can be glued together, but the gluing should be somehow symmetrical. Also the kerf (the width of the blade) should be considered.

Problem envy-free stick-division problem: Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks https://www.wild-inter.net/publications/reitzig-wild-2018


Problem 2: We are given a stick of length L. We make cuts such that the longest piece is of length n at most. What are the minimum number of pieces we will get and in how many ways this can be done? https://math.stackexchange.com/questions/2268572/number-of-ways-of-cutting-a-stick-such-that-the-longest-portion-is-of-length-n

Problem Sandwich https://www.codechef.com/MAY17/problems/SANDWICH

Cutting stick problem We are given a bundle of sticks all having integer lengths. Can we break the sticks so that the resulting sticks have lengths 1, 2, . . . , n? https://www.cse.iitb.ac.in/~jagadish/cutting_sticks_ipl.pdf https://iwriteiam.nl/cutsticks.html

Problem Minimize number of cuts required to break N length stick into N unit length sticks. https://www.geeksforgeeks.org/dsa/minimize-number-of-cuts-required-to-break-n-length-stick-into-n-unit-length-sticks/

Problem Number of ways to cut a stick of length N into in even length at most K units long pieces https://www.geeksforgeeks.org/dsa/number-of-ways-to-cut-a-stick-of-length-n-into-in-even-length-at-most-k-units-long-pieces/

Problem CSES Solutions - Stick Lengths https://www.geeksforgeeks.org/competitive-programming/cses-solutions-stick-lengths/

Problem https://www.codechef.com/practice/course/1-star-difficulty-problems/DIFF1200/problems/STICKBREAK

Parts

One gluing only

  • Bad method: very uneven cuts, and 20 cm is rather short.
    • 110cm, 90cm (1st board)
    • 20, 110 (2nd)
    • 70, 40 (2nd)
    • 110 etc. . .
  • Second method; divide into two equal parts
    • 55cm, 55 cm (1st board)
    • 55cm, 55 cm (1st and 2nd board [55x3 = 165, 35cm lost])
    • 55cm, 55 cm (2nd board)
    • 55cm, 55 cm (3rd board)
    • 55cm, 55 cm (3rd and 4th board)
    • 55cm, 55 cm (4th board)
  • Third method; divide into three equal parts
    • 36, 36, 36 (36x3 = 108, 1st board)
    • 36, 36 / 36 (36x4 = 180, 1st and 2nd board)
    • 36, 36, 36 (2nd board)
    • 36, 36, 36 (3rd board)
    • 36, 36 / 36 (3rd and 4th board)
    • 36, 36 (4th board)

Optimization

Consider

References

https://bland.ltd/cutlist/ (https://jonathan.overholt.org/projects/cutlist)

Retrieved from "https://wiki.luntti.net/index.php?title=Optimal_way_to_cut_boards_to_given_length&oldid=14477"