Задача оптимального раскроя

def FFDH(rectangles, W0):
    '''Стандартный алгоритм упаковки в полубесконечную полосу First Fit Decreasing High'''
    sorted_rectangles = sort_rectangles(rectangles)
    level_count = 1
    layout = [[((0.0, 0.0), sorted_rectangles[0])]]
    for rectangle in sorted_rectangles[1:]:
        current_x = 0.0
        packable = False
        for level in range(level_count):
            current_y = sum([lo[1][1] for lo in layout[level]])
            if current_y + rectangle[1] <= W0:
                best_level = level
                packable = True
                break
            current_x += layout[level][0][1][0]
        if not(packable):
            best_level = level_count
            level_count += 1
            layout.append([])
            current_y = 0.0
        layout[best_level].append(((current_x, current_y), rectangle))
    print(sorted_rectangles)
    print(round(calc_space_eff(layout, W0), 2))
    return layout

def BFDH(rectangles, W0):
    '''Стандартный алгоритм упаковки в полубесконечную полосу Best Fit Decreasing High'''
    sorted_rectangles = sort_rectangles(rectangles)
    level_count = 1
    layout = [[((0.0, 0.0), sorted_rectangles[0])]]
    for rectangle in sorted_rectangles[1:]:
        current_x = 0.0
        best_y = 0.0
        packable = False
        for level in range(level_count):
            current_y = sum([lo[1][1] for lo in layout[level]])
            if (current_y + rectangle[1] <= W0) and (current_y > best_y):
                best_x = current_x
                best_y = current_y
                best_level = level
                packable = True
            current_x += layout[level][0][1][0]
        if not(packable):
            best_level = level_count
            level_count += 1
            layout.append([])
            best_x = current_x
            best_y = 0.0
        layout[best_level].append(((best_x, best_y), rectangle))
    print(sorted_rectangles)
    print(round(calc_space_eff(layout, W0), 2))
    return layout

def FCNR(rectangles, W0):
    '''Cтандартный алгоритм упаковки в полубесконечную полосу Floor Ceiling No Rotating'''
    sorted_rectangles = sort_rectangles(rectangles)
    layout = [[((0.0, 0.0), sorted_rectangles[0], 'floor')]]
    level_count = len(layout)
    for rectangle in sorted_rectangles[1:]:
        current_x = 0.0
        best_y = 0.0
        packable = False
        for level in range(level_count):
            current_y = sum([lo[1][1] for lo in layout[level]])
            if (current_y + rectangle[1] <= W0) and (current_y > best_y):
                best_x = current_x
                best_y = current_y
                best_level = level
                packable = True
            current_x += layout[level][0][1][0]    
        if packable:
            layout[best_level].append(((best_x, best_y), rectangle, 'floor'))
        else:
            current_x = 0.0
            for level in range(level_count):
                current_y = sum([lo[1][1] for lo in layout[level]])
                current_y2 = 0.0
                for lo in layout[level][::-1]:
                    current_y -= lo[1][1]
                    if (lo[2] == 'ceil'):
                        current_y2 += lo[1][1]
                    if (current_y + current_y2 + rectangle[1] <= W0) and (lo[1][0] + rectangle[0] <= layout[level][0][1][0]) and (lo[2] == 'floor'):
                        best_x = current_x + layout[level][0][1][0] - rectangle[0]
                        best_y = W0 - current_y2 - rectangle[1]
                        packable = True
                        layout[level].append(((best_x, best_y), rectangle, 'ceil'))
                        break
                current_x += layout[level][0][1][0]
                if packable:
                    break
        if not(packable):
            best_level = level_count
            level_count += 1
            layout.append([])
            best_x = current_x
            best_y = 0.0
            layout[best_level].append(((best_x, best_y), rectangle, 'floor'))   
    print("Сортировка по высоте:\n", sorted_rectangles)
    print("\nКоэффициент использования (без учета узких полос):", round(calc_space_eff(layout, W0), 2))
    print("\nРаскладка:\n", layout)
    return layout

import numpy as np
def sort_rectangles(rectangles):
    '''Сортировка прямоугольников по высоте'''
    height_sorted_index = np.argsort([rectangle[0] for rectangle in rectangles])[::-1]
    sorted_rectangles = [rectangles[index] for index in height_sorted_index]
    return sorted_rectangles

def calc_space_eff(layout, W0):
    '''Вычисление коэффициента эффективности использования площади упаковки'''
    rect_sq = 0.0
    Lmax = 0.0
    for level_lo in layout:
        for rect in level_lo:
            rect_sq += rect[1][0] * rect[1][1]
            if rect[0][0] + rect[1][0] > Lmax:
                Lmax = rect[0][0] + rect[1][0]
    return rect_sq / (W0 * Lmax)

from tkinter import *
def draw_layout(layout, H0, W0, region=True, cutting=True, text=True, order=False):
    '''Отрисовка упаковки и раскладки'''
    window = Tk()
    w_width = window.winfo_screenwidth()-100
    w_height = window.winfo_screenheight()-100
    scale = 0.9*w_height/W0
    canvas = Canvas(window, width=w_width, height=w_height)
    canvas.pack()
    d = 20.0
    delta = 10.0
    canvas.create_rectangle(scale*d, scale*d, scale*(H0+d), scale*(W0+d))
    for level in layout[::-1]:
        floor_n = 0
        for rect in level:
            if len(rect) > 2:
                if rect[2] == 'floor':
                    floor_n += 1
            else:
                floor_n = len(level)
        for i, rect in enumerate(level):
            if region:
                canvas.create_rectangle(scale*(rect[0][0] + d),
                                        scale*(rect[0][1] + d),
                                        scale*(rect[0][0] + rect[1][0] + d),
                                        scale*(rect[0][1] + rect[1][1] + d),
                                        fill="light grey")
            if cutting:
                canvas.create_line(scale*(rect[0][0] + d),
                                   scale*(rect[0][1] + d - delta),
                                   scale*(rect[0][0] + d),
                                   scale*(rect[0][1] + rect[1][1] + d))
                canvas.create_line(scale*(rect[0][0] + d - delta),
                                   scale*(rect[0][1] + d),
                                   scale*(rect[0][0] + rect[1][0] + d),
                                   scale*(rect[0][1] + d))
                canvas.create_line(scale*(rect[0][0] + rect[1][0] + d - delta),
                                   scale*(rect[0][1] + d - delta),
                                   scale*(rect[0][0] + rect[1][0] + d - delta),
                                   scale*(rect[0][1] + rect[1][1] + d))
                canvas.create_line(scale*(rect[0][0] + d - delta),
                                   scale*(rect[0][1] + rect[1][1] + d - delta),
                                   scale*(rect[0][0] + rect[1][0] + d),
                                   scale*(rect[0][1] + rect[1][1] + d - delta))
            if text:
                canvas.create_text(scale*(rect[0][0] + d + 10.0),
                                   scale*(rect[0][1] + d + 5.0),
                                   text=str(i) + '; ' + str(rect),
                                   anchor='nw')
            if order:
                if rect[2] == 'floor':
                    canvas.create_text(scale*(rect[0][0] + 0.5*rect[1][0] + d),
                                        scale*(rect[0][1] + rect[1][1] + d),
                                        text=str(2*(floor_n - i) - 1),
                                        anchor='s',
                                        fill="red")
                    canvas.create_text(scale*(rect[0][0] + 0.5*rect[1][0] + d),
                                        scale*(rect[0][1] + d),
                                        text=str(2*(floor_n - i)),
                                        anchor='n',
                                        fill="red")
                    canvas.create_text(scale*(rect[0][0] + d),
                                        scale*(rect[0][1] + 0.5*rect[1][1] + d),
                                        text=str(2*floor_n + 1),
                                        anchor='w',
                                        fill="red")
                    canvas.create_text(scale*(rect[0][0] + rect[1][0] + d),
                                        scale*(rect[0][1] + 0.5*rect[1][1] + d),
                                        text=str(3*floor_n - i + 1),
                                        anchor='e',
                                        fill="red")
                else:
                    canvas.create_text(scale*(rect[0][0] + 0.5*rect[1][0] + d),
                                       scale*(rect[0][1] + rect[1][1] + d),
                                       text=str(2*(3*floor_n - i) + 3),
                                       anchor='s',
                                       fill="red")
                    canvas.create_text(scale*(rect[0][0] + 0.5*rect[1][0] + d),
                                       scale*(rect[0][1] + d),
                                       text=str(2*(3*floor_n - i) + 2),
                                       anchor='n',
                                       fill="red")
                    canvas.create_text(scale*(rect[0][0] + d),
                                       scale*(rect[0][1] + 0.5*rect[1][1] + d),
                                       text=str(2*len(level) + i + 2),
                                       anchor='w',
                                       fill="red")
                    canvas.create_text(scale*(rect[0][0] + rect[1][0] + d),
                                       scale*(rect[0][1] + 0.5*rect[1][1] + d),
                                       text=str(3*len(level) + 2),
                                       anchor='e',
                                       fill="red")
    window.mainloop()
    return