Курсовая работа: Оптимальный раскрой материала с максимальной прибылью

Здесь и далее i(l) – номер детали, которой соответствует максимальная оценка раскроя (сумма стоимости всех деталей, входящих в раскрой) f(l) на шаге l.

Рассмотрим более подробно последовательное заполнение таблицы на примере шагов

l = 7…14, 22.

1) l = 7

Выбираем первую деталь: i = 1. Длина детали 7, оценка 9.

Вычисляем остаток от раскроя: 7 – 7 = 0. Поскольку остаток нулевой, то деталей, которые можно добавить в раскрой, нет. Следовательно, максимальная оценка текущего раскроя равна f = 9. Заносим в таблицу значения i(7) = 1, f(7) = 9 и переходим к следующему шагу раскроя.

2) l = 8

Снова берём первую деталь: i = 1. Длина детали 7, оценка 9.

Остаток: 8 – 7 = 1. Так как деталей с такой длиной нет, максимальная оценкараскроя f = 9. Заносим в таблицу i(8) = 1, f(8) = 9.

3) l = 9

i = 1, остаток 9 – 7 = 2, f = 9.

Заносим в таблицу i(9) = 1, f(9) = 9.

4) l = 10

i = 1, остаток 10 – 7 = 3, f = 9.

Заносим в таблицу i(10) = 1, f(10) = 9.

5) l = 11

i = 1, остаток 11 – 7 = 4, f = 9.

Учитывая, что в текущий раскрой также уместится деталь i = 2 c длиной 11, получим:i = 2, остаток 11 – 11 = 0, f = 14.

Сравним оценки раскроев. Выберем максимальную оценку (f = 14) и соответствующую ей деталь (i = 2).

Заносим в таблицу i(11) = 2, f(11) = 14.

6) l = 12

i = 1, остаток 12 – 7 = 5, f = 9.

i = 2, остаток 12 – 11 = 1, f = 14 (максимум)

Заносим в таблицу i(12) = 2, f(12) = 14.

7) l = 13

i = 1, остаток 13 – 7 = 6, f = 9.

i = 2, остаток 13 – 11 = 2, f = 14.

i = 3, остаток 13 – 13 = 0, f = 16 (максимум)

Заносим в таблицу i(13) = 3, f(13) = 16.