У меня имеются прямоугольники и квадраты размерами:
1х1, 1х2, 2х2.
Необходимо максимально эффективно упаковывать произвольные фигуры (они могут быть любые, с повторениями) этих размеров в ящик размером 4х3.
Фигура 1х2 при необходимости должна переворачиваться в 2х1.
Задачу про рюкзак читал, видел, алгоритмы смотрел, на PHP найти такое не смог.
Может кто-нибудь мог бы хотя бы навести на ключ к решению задачи?
Заранее спасибо.
сколько фигур и каких фигур есть? есть установленная полезная ценность у фигур?
при такой постановке задачи можно просто сказать что сначала большую саму берем заполняем максимально ими, потом меньше, и в последнюю очередь 1*1
Шаров Дмитрий: Полезной ценности у фигур нет, пихать можно как угодно. Важным условием является только возможность поворачивать фигуру 2х1 для лучшей оптимизации. Спасибо за совет, попробую наполнять так
Дальше строим все вариации заполнения. Из полученных выбираем наиболее оптимальную (максимально эффективно), хотя тут бы я на Вашем месте уточнил, что считать максимально эффективным.
Задача рюкзака вообще NPполная, на PHP будет считаться веками. В вашей частной формулировке задача решается без замысловатых алгоритмов. Считайте эталонной упаковкой - два больших квадрата(их больше не влезет) на которых лежат две палки(больше не влезет). Далее большой квадрат может быть заменен двумя палками, а палка двумя малыми квадратами - так вы получите дерево всех оптимальных решений. Оно небольшое.
