Учим питон (или пайтон)

[_Swetlana]

Мой FFD дает такой же результат, как ИИ. Но у меня ООП, в отличии от.
Правда, класс "палка" я не стала создавать, чтобы не усложнять ввод данных. Создала только класс шест 

Код Выделить Развернуть

class Pole:
    pcount = 0
   
    def __init__(self):
        self.length = 6000
        self.stics = []

    def add_stic(self, lstick):
        if lstick <= self.length:
            if self.length == 6000: # начинаем новый контейнер
                Pole.pcount += 1
            self.length -= lstick
            self.stics.append(lstick)
            return True
        else:
            return False


stics = [2200]*40 + [1429]*40 + [680]*40 + [496]*20 + [450]*40 + [170]*20
poles = [Pole() for _ in range(40)]

for stic in stics:
    for p in poles:
        if p.add_stic(stic):
            break
print('Использованных контейнеров:', Pole.pcount)
for p in poles:
    print(6000 - p.length, end=' ')
Использованных контейнеров: 35
5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5716 5716 5716 5716 5716 5936 5936 5936 5936 5936 5952 5988 5850 5850 1800 0 0 0 0 0

[Hellerick]

Для полуавтоматической раскладки я сделал себе такую перебиралку:

Код Выделить Развернуть

sticks = {
    2200: 40,
    1429: 40,
    680: 40,
    496: 20,
    450: 40,
    170: 20}

pole_length = 6000

stick_lengths = sorted([l for l in sticks], reverse=True)

def vary(inlayouts, depth):
    check_qty = min(
        pole_length//stick_lengths[depth],
        sticks[stick_lengths[depth]],
        )
    outlayouts = []
    if depth == len(stick_lengths)-1:
        for i in range(check_qty+1):
            outlayouts = outlayouts + [inlayouts + [i]]
    else:
        for i in range(check_qty+1):
            outlayouts = outlayouts + vary(inlayouts+[i], depth+1)
    return outlayouts

layouts = vary([], 0)

def layout_total_len(layout):
    return sum([layout[i]*stick_lengths[i] for i in range(len(layout))])

layouts = [l for l in layouts if layout_total_len(l) <= pole_length and sum(l)>0]

layouts.sort(key = layout_total_len, reverse = True)

print(f'Number of layouts found: {len(layouts)}')

print(f'For sticks with lengths\n{stick_lengths}\n')

print(f'Best layouts:')
for l in layouts[:400]:
    print(f'{l}, L={layout_total_len(l)}')

Она мне печатает наиболее удачные возможные раскладки:

Код Выделить Развернуть

Number of layouts found: 6350
For sticks with lengths
[2200, 1429, 680, 496, 450, 170]

Best layouts:
[0, 0, 3, 0, 2, 18], L=6000
[0, 0, 4, 0, 2, 14], L=6000
[0, 0, 5, 0, 2, 10], L=6000
[0, 0, 6, 0, 2, 6], L=6000
[0, 0, 7, 0, 2, 2], L=6000
[0, 2, 0, 2, 1, 10], L=6000
[0, 2, 1, 2, 1, 6], L=6000
[0, 2, 2, 2, 1, 2], L=6000
[0, 1, 0, 0, 6, 11], L=5999
[0, 1, 0, 5, 2, 7], L=5999
[0, 1, 1, 0, 6, 7], L=5999
[0, 1, 1, 5, 2, 3], L=5999
[0, 1, 2, 0, 6, 3], L=5999
[1, 1, 0, 0, 3, 6], L=5999
[1, 1, 1, 0, 3, 2], L=5999
[2, 1, 0, 0, 0, 1], L=5999
[0, 0, 0, 3, 7, 8], L=5998
[0, 0, 0, 8, 3, 4], L=5998
[0, 0, 1, 3, 7, 4], L=5998
[0, 0, 1, 8, 3, 0], L=5998
[0, 0, 2, 3, 7, 0], L=5998
[1, 0, 0, 3, 4, 3], L=5998
[0, 1, 0, 1, 3, 16], L=5995
[0, 1, 1, 1, 3, 12], L=5995
[0, 1, 2, 1, 3, 8], L=5995
[0, 1, 3, 1, 3, 4], L=5995
[0, 1, 4, 1, 3, 0], L=5995
[1, 1, 0, 1, 0, 11], L=5995
[1, 1, 1, 1, 0, 7], L=5995
[1, 1, 2, 1, 0, 3], L=5995
...

Среди найденных вариантов я выбираю те, которые кажутся перспективными.
Перспективные раскладки — те, которые можно многократно повторять, то есть рабочий может нарезать эту раскладку несколько раз, избавляя нас от наиболее длинных палок, но при этом оставляя разумное количество коротких палок для дальнейших раскладок. Наверное, перспективную "хорошесть" раскладки можно как-то оценить численно.
Выбрав одну раскладку, и "нарезав" по ней палки, я прогоняю скрипт повторно, уже с меньшим набором требуемых палок. Чем дальше, тем меньше остается выбор, и тем меньше "мощность" задачи по перебору вариантов.

Короче, при осознанном подходе, у задачи не такое уж великое ветвление, и разумные варианты там вполне посильно перебрать.

[_Swetlana]

Среди найденных вариантов я выбираю те, которые кажутся перспективными.
Перспективные раскладки — те, которые можно многократно повторять, то есть рабочий может нарезать эту раскладку несколько раз.

Вот это правильно, повторяющиеся раскладки. Тем более, данные у вас уж очень регулярные - каждого вида по 40 штук.
Как-то решала задачу, там разрезалась стальная полоса на полосы определенной ширины, и вот эти ширины набирались с помощью втулок, которые на листе выставлялись. И нужно было не просто набрать нужные суммы (ширины), а набрать минимальным числом втулок, чтобы резчику не приходилось долго это всё выкладывать.
Ну та задача решалась динамическим программированием.
Потом я ее в свой учебник вставила, вот она:

Задание 3 (высокий уровень)
Линия продольной резки рулонного металла вырезает из рулона полосу определённой ширины. У резчика имеется набор втулок разной ширины. Набрать заданную ширину с помощью имеющихся втулок так, чтобы количество использованных втулок было минимально. Исходные данные придумать самому, набор должен содержать не менее 25 втулок, в наборе могут быть втулки одинаковой ширины.

[H_N]

Не программист я и не математик. Зацепила реплика Hellerick'а, что ИИ сработал хуже человека. Попробовал и сам поискать решение его задачи. Действовал тупым перебором вариантов. Тактика простая: поначалу компоновал крупняк. Удачно подошли 20 раскроек по 5999 мм. Далее по убыванию... Итог: влез в 35-ый шест на 450 мм. Остаток, соответственно, 5550 мм. Был и промежуточный — 5100, но я нашёл и лучший.

2200*2 + 1429*1 + 170*1 =               5999 (20 шт.)
1429*3 + 680*1 + 496*2 =                5959 (5 шт.)
1429*1 + 680*2 + 496*1 + 450*6 =        5985 (2 шт.)
1429*1 + 680*3 + 496*2 + 450*3 =    5811 (1 шт.)   
1429*1 + 450*10 =                   5929 (2 шт.)
680*6 + 496*2 + 450*2 =             5972 (2 шт.)
680*8 + 496*1 =                     5936 (2 шт.)
450*1 =                              450 (1 шт.)                         

[_Swetlana]

Не программист я и не математик. Зацепила реплика Hellerick'а, что ИИ сработал хуже человека.

@Hellerick А что там за ИИ-то был? Не яндексовский, надеюсь?

Так ИИ просили использовать минимальное количество шестов. Что он и сделал.
Нужно как-то формализовать наши дальнейшие хотелки, иначе многокритериальная оптимизация получится, а это другая задача.
Из всех минимальных упаковок в 35 шестов выбрать ту самую ... Ну давайте подумаем, что мы тут максимизируем.
У каждого шеста вычисляем длину "огрызка". У меня она прямо в атрибуте экземпляра хранится, и вычислять не надо. Далее, среди всех шестов находим максимальный огрызок.
Вопрос к ИИ. При таких-то исходных данных среди всех упаковок в 35 шестов найти упаковку, у которой длина максимального огрызка максимальна.

[Hellerick]

А что там за ИИ-то был?

Если не ошибаюсь, я использовал модель claude-3-haiku вот здесь:
https://labs.perplexity.ai/

Нужно как-то формализовать наши дальнейшие хотелки

Ны дык:

Критерий оптимизации: список `remainders`, содержащий в себе неиспользуемые остатки каждого шеста, отсортированный в порядке убывания, должен быть как можно больше (в том смысле, в котором в питоне сравниваются два списка). То есть, надо использовать как можно меньше шестов, при этом от использованных шестов надо оставить как можно бо́льшие остатки.

Для моего решения:

2200×2 + 680×1 + 450×2 = 5980 (20 poles)
1429×3 + 680×2 + 170×2 = 5987 (10 poles)
1429×2 + 496×6 = 5834 (3 poles)
1429×4 = 5716 (1 pole)
496×2 = 992 (1 pole)

остатки будут равны:
remainders = [5008, 284, 166, 166, 166, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13]

Задача -- найти раскладку, для которого отсортированный массив остатков будет наибольшим.

[_Swetlana]

(в том смысле, в котором в питоне сравниваются два списка).

понятно

Ну тут как можно. FFD сформировать начальное решение. В скобках замечу, что по числу использованных шестов оно будет минимальным. А потом методом локального поиска пытаться улучшить упаковку. Например, делать обмены. Выбирать пару шестов, пусть они обмениваются палками. Если целевая функция улучшилась, то делать обмен. Давно я такое делала для равномерного распределения работ между бригадами, но подробности плохо помню. 

[Hellerick]

Найти бы хотя бы просто "недетерминированный" алгоритм, который перебирает варианты, вместо того, чтобы выдавать единственный.
А уж выбрать из них хороший — не проблема.

[_Swetlana]

Найти бы хотя бы просто "недетерминированный" алгоритм, который перебирает варианты, вместо того, чтобы выдавать единственный.
А уж выбрать из них хороший — не проблема.

Да запросто. Ещё одна неглубокая идея 
В оптимальной упаковке не может быть двух контейнеров, заполненных не более чем наполовину. Иначе бы мы сложили их содержимое в один контейнер и уменьшили целевую функцию.
Что отсюда следует. А то, что n-1 контейнер заполнен более чем на половину и только один-единственный может быть заполнен менее чем на половину. Так какой смысл пытаться уплотнить упаковку сразу во всех контейнерах? За этот один и возьмёмся, будем максимизировать "огрызок" в одном контейнере. Делать это можно локальным поиском: найдём решение FFD-алгоритмом, затем будем искать лучшее решение в его окрестности. Допустимые операции: одна палка перекладывается из одного контейнера в другой; две палки из разных контейнеров меняются местами. 

[_Swetlana]

Какая гадость эта ваша динамическая типизация.
ссылка на яндекс-диск

[Vesle Anne]

Найти бы хотя бы просто "недетерминированный" алгоритм, который перебирает варианты, вместо того, чтобы выдавать единственный.
А уж выбрать из них хороший — не проблема.

рл вам в помощь

[Hellerick]

Кстати.
Я еще в школе написал программку, находившую кратчайший маршрут в московском метро.
Но для меня по-прежнему загадка, как находить второй по краткости маршрут.

[_Swetlana]

Кстати.
Я еще в школе написал программку, находившую кратчайший маршрут в московском метро.
Но для меня по-прежнему загадка, как находить второй по краткости маршрут.

Алгоритм Йена находит первые k маршрутов.