Всем доброго времени! Ко нибудь решал такую задачу? На поддон нужно разложить коробки оптимальным образом. коробки будут только в один ряд, т.е. нам важно только двумерное расположение.

google://задача+о+рюкзаке

(0) Сколько платишь?

(2) Мне не готовый код нужен, а хотя бы идея

(1) О рюкзаке не подойдет.
Поддоны разные, сколько типоразмеров?
Сколько типоразмеров коробок?
Коробки можно переворачивать, или низ определен?

(3) Дам даже две идеи:
1. Изучить и написать самому
2. Нанять кто уже изучил, за денежку

(4) Поддоны одинаковые. Высота коробок всегда одинакова, поэтому высоту не рассматриваем. Встречаются одинаковые коробки.Попробую объяснить так. Коробки это слова, разного шрифта и разной длины, на строчке желательно писать слова одного шрифта, максимальное количество слов на строчку. Лист куда пишем может быть или альбомной ориентации или портретом

(6) Таблички/вывески делаете?

Начни с тупого полного перебора всех вариантов.
Если "коробок" на "поддоне" меньше ста это вполне вменяемое время.

(7) нет, именно поддоны

Длина в степени ширина?

КоличествоКоробок!

! = https://ru.wikipedia.org/wiki/Факториал

(6) Если правильно понял, набор "коробок" неизвестен.В каждом случае свои.
Пробовал давно (лет 25 назад) аналогичное делать для раскроя металла, результат был так себе (средний выход был примерно 80%).
Да и идеи особой не было: какая-то реализация схемы ветвей и границ.
Обычно оператор с этим справляется неплохо: что-то типа тетриса.

Сорри я ошибся с "меньше ста", там уже после 10 коробок цифры не вменяемые количество вариантов для полного перебора.

(13) Тут как понял упрощение есть что часть коробок одинаковые

(15) Но есть усложнение, желательно в одну строчку одинакового шрифта

(16) Это еще упрощение же, меньше вариантов.

"коробки это слова"©
Да, алкоголь - действительно зло
..

(18) Не пью, а может стоит начать) Я уж пытался оъяснить как мог

(19) ну так критерий оптимизации - какой?

Есть классическая работа Канторовича по раскрою фанеры.
Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов.
https://www.studmed.ru/kantorovich-lv-zalgaller-va-racionalnyy-raskroy-promyshlennyh-materialov_a38c352d1f8.html
но мне кажется там другая задача, т.к дело сводится к задаче линейного программирования.
В любом случае нужно в Инете поискать.

(14) Да, немало
Факториал = 1;
    Для а = 1 По 10 Цикл
        
        Факториал = Факториал*а;
        
    КонецЦикла;

Если даже пользователь будет готов подождать, понятия не имею как обходить свой ТЗ

Длина|Ширина|Количество

(21) у Канторовича понятен критерий оптимизации. Что является критерием у ТС - неизвестно.

Сначала сгруппируй свои коробки в три вида групп:
1. Одинаковые
2. Одной длины
3. Одной ширины

Затем отсортируй внутри групп и начинай перебирать, укладывая в прямоугольник.
Укладка это записи в новую ТЗ, где координаты верхнего-левого угла каждой коробки и ссылка на описание коробки (номер из первой ТЗ)

(24) Угу одно дело засунуть в стандартные размеры (максимум коробок или их веса) и совсем другое засунуть все в минимальную площадь.

(24) Так же: минимум отходов. Если правильно понял задачу.

(25)
Первая группа
h1 X a1 - 5шт
h2 X a2 - 8шт
h3 X a1 - 4шт

Вторая группа
h1 X a1 - 5шт
h1 X a2 - 3шт
h1 X a3 - 9шт

Третья группа
h1 X a1 - 5шт
h2 X a1 - 2шт
h3 X a1 - 4шт

НовСтр = ТЗ_Укладка.Добавить();
НовСтр.Коробка = ?

Ссылок у меня нет, работа только цифрами

(27) далеко не факт. Кроме "расположить оптимальным образом" - критериев нет

+(29) равно как нет и явно описанных ограничений ..

(25) Не догоняю

(31) ставь любые и хоть как - любое расположение будет оптимальным

https://какой-тосайт/public/267268/

http://www.packer3d.ru/online/pal-by-box

3д пакер

на ИС - у Ильдаровича есть решение задачи запросом.
я с ним контачил, оптимальности при укладке нескольких слоев даже в простом варианте не давала, но в один слой возможно разложит

да, вот она в 33 упомянута

В экселе есть метод решения подобных задач, называется симплекс-метод

Я подобные задачи решал перебором. Но тупо перебор это очень много, и там идут большие отсеивания вариантов, которые заведомо дальше не приведут к решению или к улучшению того что уже найдено. Для примера, исходное множество элементов сортируется по возрастанию размеров, и начинаем перебор. Если после заполнения некоторого объема следующий не влезает, значит все последующие то же не влезут. И лучше такое делать на компилируемом языке, а не на 1С, на порядки больше вариантом перебрать можно. И еще, если кол-во растановок больше чем можно перебрать, то можно делать перебор случайных вариантов и выбирать лучший из тех, что перебрались за отведенное время.

В данных задачах нельзя искать самый лучший вариант. Достаточно найти не плохой вариант, который полностью определяется выбранным алгоритмом. К примеру разница в эфективности подбора варианта будет 1%, но улучшение на эти 1% потребует увеличение затрат на рассчет в 1000 раз. Смысла в этом нет.

Я в свое время решал задачу оптимального бронирования гостинничного фонда. Достаточно простая задача

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

(40) А какой перебор был? Без перебора? Т.е. существует алгоритм который может решать такие вещи без факториальной составляющей? Будет интересно почитать. 1%, или 5%, или 0.01% - где критерий, что именно этот процент будет проблемным? Все зависит от задачи, от критерия отбора вариантов, от реализации. Если комп может перебрать все варианты за 0.5 секунды, то зачем ему мешать и ограничивать? А если не может за час, то просто определяем, сколько ему позволительно считать, и вмещаем в это время все что сможем без оглядки на оставшиеся варианты. Если при этом отбирать без условно случайной выборки, то может оказаться, что перебор все это время перебирал область, где нет решений, а решения сидели группой где-то рядом.

(40) тут даже может, что сделал этот алгоритм для одной организации. А потом приходиш в другую, той же фигней занимающеся. И эти новые говорят, а вот мы организация по крупней, у нас паллеты покрупней, и на них на пять коробочек больше помещается. И прежний алгоритм сядет в лужу, т.к. факториал от дополнительных пяти коробочек уже может оказаться не перебираемым.

(36) Симплекс-метод - один из методов решения задачи линейного программирования.
У автора другая задача.

Я смотрю, задача многим понравилась, но никто или не решал или не подсказал как решать. Перебор не могу осуществить, для начала пусть даже он будет долгим.

(44) чем размещение "3*4" будет оптимальней размещения "2*6"?

(45) Больше площади займет на поддоне

Теперь я уже просто хочу оптимальный ряд построить. т.е. одномерно.

(44) Может для начала приведёшь входные условия(поддоны одинаковые?) и критерии оптимальности(минимальное количество поддонов для заданного набора коробок?)

От меня до двери 12 метров. У меня есть палочки
2м-3шт
4м-1шт
1.5м-2шт
2.5м-1шт

Какие выбрать палочки и расставить на эти 12м, чтоб расстояние без палочек осталось минимальным?

Ух пропустил я занятия про рекурсию)  так и не умею использовать

ВЫБРАТЬ
    ВТ.Ширина
ПОМЕСТИТЬ ВТ
ИЗ
    &ВТ КАК ВТ
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    ВТ.Ширина,
    ВТ1.Ширина КАК Ширина1,
    ВТ2.Ширина КАК Ширина2,
    ВТ3.Ширина КАК Ширина3,
    ВТ4.Ширина КАК Ширина4,
    ВТ.Ширина + ВТ1.Ширина + ВТ2.Ширина + ВТ3.Ширина + ВТ4.Ширина КАК Сумма
ПОМЕСТИТЬ ВТ_Рез
ИЗ
    ВТ КАК ВТ,
    ВТ КАК ВТ1,
    ВТ КАК ВТ2,
    ВТ КАК ВТ3,
    ВТ КАК ВТ4
ГДЕ
    ВТ.Ширина + ВТ1.Ширина + ВТ2.Ширина + ВТ3.Ширина + ВТ4.Ширина <= 12
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    ВТ_Рез.Ширина,
    ВТ_Рез.Ширина1,
    ВТ_Рез.Ширина2,
    ВТ_Рез.Ширина3,
    ВТ_Рез.Ширина4,
    МАКСИМУМ(ВТ_Рез.Сумма) КАК Сумма
ИЗ
    ВТ_Рез КАК ВТ_Рез

СГРУППИРОВАТЬ ПО
    ВТ_Рез.Ширина,
    ВТ_Рез.Ширина1,
    ВТ_Рез.Ширина2,
    ВТ_Рез.Ширина3,
    ВТ_Рез.Ширина4

А здесь уже отбирать по количествам вхождений

(49) Это классическая задача о ранце (правда коэффициенты в критерии совпадают с коэффициентами в ограничении).

(46) т.е. площадь суммы не равна сумме площадей? у вас какая-то отдельная математика?

(49) В такой постановке задача совсем детская.
  Берешь самую длинную палку, потом самую длинную из тех которые помещаются и дальше по кругу.
   Вот и весь алгоритм.
Я уверен на для большого набора возможных палок в 99% случаев решение будет оптимальным. Особенно если рядов будет больше 2-х

По поводу оптимального раскроя в 2D задача более интересная. Но и она в определенных приближениях решается в 30 строк кода. В этих приближениях 3х4 лучше чем 2х6

(53) Не совсем понимаю, может на примерах?

(54) согласен что в начале большие брать, но это не всегда оптимально. первый всегда самый длинный

(54) Это называется жадный алгоритм

(56) есть 12 коробок, площадью 100 кв.см.
расположив эти 12 коробок в 3 ряда по 4 штуки это займет площадь 1200 кв см.
расположив 12 коробок в 2 ряда по 6 штук они займут площадь в 1200 кв.см.
почему какой-то вариант "больше площади займет на поддоне"?
-------------
впрочем,Ю критерии оптимальности у вас все-таки вытащили - минимальная незанятая плошадь.
и ограничения тоже - все коробки равноценные.
нет еще одного ограничения - количества коробок...

говорят задачу расположения коробок можно даже на скл решить

(54) далеко не всегда.
представь для паллета 10*10 набор из одной коробки 9*9, и двадцати коробок 1*5.

(59) а у меня то коробки разные. например поставил на поддон 2 самые большие коробки, туда ничего уже не поставишь. все маленькие на второй поддон и еще немного на третий поддон. А можно сделать так: на поддон только одну большую коробку, остальное место мелким коробками. Второй поддон так же, глядишь, третий поддон и не понадобится

(62) я тебе пример приводил для 12 одинаковых коробок.  Именно чтоб вытянуть критерий оптимальности.
-------
"глядишь, третий поддон и не понадобится" -
следовательно, у тебя критерий - количество поддонов, а не свободное место на поддоне.

(54) Жадный алгоритм в задаче о ранце не всегда дает оптимальное решение.
Пример: 5,4,3,2. Нужно набрать для 10.
Жадный: 5+4. Оптимально: 5+3+2.

(60) Можно, но лучше не решать. Поскольку размер матрицы вариантов поражает воображение при более менее серьезной размерности задачи.

(64) у жадного алгоритма первый выбор де должен отсекать оптимальные решения. а у ранца это не всегда так.

(44) Задача то стандартная, но точного решения не имеет.

(67) точное  и не обязательно. и точных можнт быть множество, или не быть вообще

(68) Мне это прекрасно понятно, писал топикстартеру в ответ на его удивление, почему никто еще не подсказал "правильное решения" )

(51) А это почему никто не заценил?)

(70) Вы бы содержательно объяснили, как собираетесь решать.

(70) Потому что решать подобные задачи запросами могут только "Ильдаровичи"

(72)+ Имхо это "через задницу" - вроде как и да оно может и работает.... Но в реальных условиях такое можно применять только если нет другого выхода.

Если у тебя клиента/сервера 1С совсем дохлая например и приходится все на sql сервер отправлять для вычислений, который супер-пупер крутой и мощный.

(73) Я работаю только с цифрами. Из базы данных ничего не беру, следовательно, я думал запрос в цикле не так страшно

может проще загуглить алгоритм решения задачи раскроя

(70) потому, что это надо оценивать психиатру?

(74) Как раз если бы много брал из базы - это могло быть обосновано, через запросы.

Но млин нафуй так извращаться с "только цифрами" ?

Вы программировать совсем не умеете на языке 1С? Только запросы и СКД да?

(77) Возможно да. Но сколько тут пишем, никто еще не предложил, даже неработающий код перебора палок от меня до двери (49)

(78) А сам я не знаю как его написать, это я честно признаю

(78) полное решение можно сделать только через перебор в глубину (всех вариантов)

(75) Если даже я найду что то подходящее, там все шаблонно. А свое решение всегда проще дорабатывать. У пользователя аппетит придет во время еды, ни вам ли это знать

(78) для линейного списка - обычный бэктрекинг.
азбука жеж. а вот для двумерного уже сложнее - объемы растут и не квадратично. а есдли двухмерное с ориентацией - еще хуже

(82) Ну напиши мне неучу эту азбуку в нескольких строчках. входные данные есть

(83) полный перебор тебе написать?

(84) да, хотя бы в 3-х строчках

(83)
Вирт "Алгоритмы + структуры данных = программы."
Глава 3. Рекурсивные алгоритмы
3.4. Алгоритмы с возвратом

Коробочки с совпадающим одним размером можно попытаться обьединить в группы,группы также могут быть обьединены в группы.
опять же,ориентация коробочек тоже играет роль,т.к.например,поворот на 30 градусов одной коробочки может давать более оптимальное размещение.

(87) на 30 нет, только 90

(87) на 30? оригинально...

(86) Хотя бы ссылку. Говорите это все просто, ну хотя бы какое то начало дайте

Запутался в своих запросах

(89) задумался, вполне применимо ) представьте что есть квадратная дырка и прямоугольная коробка. Теоретически может помочь вращение. Свежий взгляд для меня.

(92) ну ты ещё в параметры вазелин введи...
ЗЫ. "Дырка бывает только в ***!".

(93) Про дырки не гоните, есть даже вполне общепринятые термины аля "дырочная проводимость". Не говоря уж о черной дыре.

(87) Интересно, правда есть решения при которых неортогональное размещение плотнее ортогонального?

(95) Думаю, можно придумать пример. Почему нет?

(95) Пример: Вырожденный случай 1 поддона и одной узкой длинной коробки.

(97) порви шаблон - поставь ее вертикально!

(98) Ок, у нас телевизор ) И вертикально не поможет, тк эта скотина плоская.

а еще можно разрешить разрезать коробки на более мелкие.

Можно засунуть коробки в коробку и хорошо потрясти - авось сами утрясутся как надо

(101) можно под пресс - тогда вероятность вписать в заданный размер сильно повышается...

Можно визуализировать задачу и подсовывать в качестве игры на корпоративном портале офисным работникам.

(103) тетрис на деньги?

(104) Бесплатный. Все равно половину времени работники прокрастинируют на мисте.

(105) BTW, за последние 6 лет я не встретил ни одного коллеги, который сидит на мисте постоянно или хотя бы периодически.
До этого - в одной конторе сразу трое..

(106)
"Валико, восемь баранов было. Один баран куда делся?
— А себя ты посчитал?
— Нет.
— Так восемь с тобой было.
— А! (пастуху) Восемь со мной было!"
©Мимино

(104) Году в 1988 был на Уралмаше. Японская установка (газорезка) по раскрою листов металла.
Сам раскрой подбирали операторы на компе: вроде тетриса.
Их премировали за сверхнормативный выход металла - люди с удовольствием этим занимались.

(0) Я бы попробовал для начала примитивный подход:
1. Группировать детали по ширине (можно с допуском).
2. Группы по ширине упорядочить по убыванию.
3. Внутри групп упорядочить по длине по убыванию.
4. Располагать на листе "жадным" образом в соответствии с этими сортировками.

(108) еще нужно посмотреть на вариативность деталей.
ну и на необходимость этих деталей...
а то где-то недавно попададось: из отходов при производстве детали делали какие-то мелкие детальки - чтоб в лом не сдавать, и все такое. премии за экономию, всё такое... а оказалось, что эти детальки были запчастью к какому-то давно снятому с производства оборудованию, и они уже года четыре тупо накапливались на складе мертвым грузом...