Пусть даны n типов заготовок с номерами 1,...,n и длинами , а исходные стержни имеют длину .
В начале поиска полагаем i=1
1. Ищем максимально возможное число заготовок типа i. Оно, очевидно, равно , где [х] - целая часть числа x.
2. Ищем длину незадействованной части стержня. Она, очевидно, равна
3. Если существует заготовка с номером, большим i, и длиной, меньшей S', и решаем аналогичную задачу для стержня длиной S' и заготовок с номерами i+1,...,n. Иначе пункт 4.
4. Получен вариант раскроя. Записываем число отходов.
5. Если N≥1 и i≠n, уменьшаем N на 1, и решаем аналогичную задачу для стержня длиной и заготовок с номерами i+1,...,n
Answers & Comments
Verified answer
Пошаговое объяснение: в приложении
Построение раскроев
Пусть даны n типов заготовок с номерами 1,...,n и длинами
, а исходные стержни имеют длину 
.
В начале поиска полагаем i=1
1. Ищем максимально возможное число заготовок типа i. Оно, очевидно, равно![N=\left[\dfrac{S}{p_i}\right]](https://tex.z-dn.net/?f=N%3D%5Cleft%5B%5Cdfrac%7BS%7D%7Bp_i%7D%5Cright%5D "N=\left[\dfrac{S}{p_i}\right]")
, где [х] - целая часть числа x.
2. Ищем длину незадействованной части стержня. Она, очевидно, равна
3. Если существует заготовка с номером, большим i, и длиной, меньшей S', и решаем аналогичную задачу для стержня длиной S' и заготовок с номерами i+1,...,n. Иначе пункт 4.
4. Получен вариант раскроя. Записываем число отходов.
5. Если N≥1 и i≠n, уменьшаем N на 1, и решаем аналогичную задачу для стержня длиной
и заготовок с номерами i+1,...,n
https://znanija.com/task/40724094?utm_source=android&utm_medium=share&utm_campaign=question
https://znanija.com/task/40724036?utm_source=android&utm_medium=share&utm_campaign=question