Комментарии 10
Отсортировать круги по размеру и брать с двух концов сразу? В примере весь третий лист мог бы войти в два предыдущих.
Вот кстати да, вы хорошо сформулировали "претензию" к алгоритму, что слишком много пустот остаётся на листе. Плюс, если это для раскроя, то совсем не обрабатывается уменьшение холостого хода раскроечной головки (что там, лазер, или плазма или другое).
Плюс, если на ртсунках реальный результат алгоритма, то видно, что много кругов "посажены" не вкрай, а значит, теряется расстояние по длине.
Я бы сделал иначе - мы в угол листа выставляем первый, самый большой круг, и в полученный уголок страницы мы вписываем наиболее большой подходящий в него круг по размеру
Мне опыт подсказывает, что отсортировано правильно, но каждый следующий круг надо класть не вверх, а искать место по всему листу как можно ниже (левее?). То есть сначала идут большие круги, и как только дело дойдёт до круга, который поместится в уголок, туда его и помещать. Ниже уже написали, как выбрать наилучшее место на листе из всех возможных.
При "установке" очередного круга рассчитывать заполнители (как в диаграммах Вороного). Потом из пула "свободных" кругов сначала подбирать круги максимально вписывающиеся в заполнители. Если ничего подобрать не получилось - размещаем самый большой доступный круг в конец листа. При "установке" в заполнитель если новый круг при пересекает один или несколько заполнителей - удаляем все пересечения и пересчитываем заполнители для установленного круга. Самое сложное будет - найти места для заполнителей.
Попытался нарисовать как это должно работать
Синие - это места-заполнители, красная стрелка - добавленный круг.
3й лист явно лишний. Я бы попробовал сротировать через один. Сначала самый большой потом самый маленький. Как колоду карт.
А я бы попробовал использовать SMT-решатель Z3.
Нет смысла искать логичное решение, это стандартная NP-полная задача о рюкзаке.
Упаковка N кругов различных диаметров на X листов (прямоугольников), заданных габаритов