Как максимально эффективно разместить элементы на площади?

Question

[Sarkis Arutiunian]

Условие задачи:
У нас есть площадь с заданными пропорциями, скажем:
const area = [100, 200];
Первый элемент в массиве высота, второй ширина. И у нас есть массив с элементами:

const items = [
[10, 4],
[20, 30],
[25, 3],
...
];

Нам нужно функция которая будет принимать два аргумента, первый площадь и второй элементы:
function resolve(area, items) {...};
Которая будет возвращать объект с двумя массивами:

console.log(resolve(area, items));
// { solved: [[4, 10], [20, 30], [3, 25]...], exclude: [[50, 60],[2, 100]...]};

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

Решение может быть на любом языке или простой math. формулой, буду благодарен за любую помощь, спасибо!

Comments

[Andrey Dugin]

А привязка элементов к координатам не нужна? Что значит "в правильном порядке"?

[alex-1917]

ну видимо ему надо именно полностью заполнять

[Sarkis Arutiunian]

Андрей Дугин, правильный порядок и позиция и будут координатами, скажем у нас есть ширина 100, и мы хотим поместить элементы [[10, 2], [90, 50], [20, 5]], последний элемент будет перенесен на следующую строку/уровень, под предыдущие элементы

Answer 1

[Sarkis Arutiunian]

я думаю это наиболее точное решение из всего что я нашел:
rosettacode.org/wiki/Knapsack_problem

Answer 2

[longclaps]

Задача об укладке ранца не имеет решения "math. формулой".
Ваш случай несколько проще из-за дискретности.
Нормальная тема для fl, при условии, что есть понимание, что задачи оптимизации не всегда решаются оптимальным из всех возможных способом )

Answer 3

[alex-1917]

Хаха, насмешили. Хотя год назад, когда взялся за похожий проект, я тоже был в таких же розовых очках)))
В итоге проект обошелся в 200к.
Общая схема такая:
1. в БД вбиваете координаты ВСЕХ точек вашего участка, т.е. 100*200=20000 точек (у меня было 1000*1000)
2. я делал на php - получаю входящий запрос на нужный размер, например нужен прямоугольник 12*7, выбираю из БД массив свободных точек, далее в php обрабатываю его, там на 300 строчек скрипт получился.
3. далее возврат в БД - помечаю все точки из выбранного места меткой ЗАНЯТО
и т.д.

У вас конечно принципиально другая задача, но сложность однозначно похожая!

Comments

[Exploding]

А как решается вопрос с оптимальным расположением элементов?

[Dimonchik]

как и в задаче: минимумом (максимум) и перестановками, т.е. полным или неполным перебором

[alex-1917]

Exploding, как как - каждый следующий запрос на новое размещение начинает искать незанятые подходящие по размеры области сверху, т.е. заполнение сверху порядно

[alex-1917]

zhornikov, практическое применение? - был запущен сервис. правда, он заглох месяца через три по другим причинам, главное, что я успел урвать полную оплату))))

[alex-1917]

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

[Exploding]

alex-1917, Ну это не решение оптимального расположения всех элементов. Это просто "впихнуть где свободно". Под оптимальным расположением я имею ввиду, например, алгоритм раскроя листов ДСП, ткани и т.д., который принимает в качестве входящих данных все элементы (детали) и комбинирует их расстановку для достижения определенных условий, это например может быть:
- минимизация трудозатрат (выполнить раскрой с наименьшим кол-вом "резов")
- минимизировать кол-во "остаточных" делатей, (чтобы остаток стремился к одной детали или наименьшему возможному кол-ву)

[alex-1917]

Exploding, да что угодно может быть, я это отразил в строке, выделенной жирным. Так как судя по настроению вопрошающего, он рассчитывает что дело проще пареной репы, поэтому я чуть-чуть сориентировал по стоимости, в которую обошелся мой вариант, думаю, это равнозначно сложности....