Задача о рюкзаке PHP. Как упаковать формы?

Question

[MassTek]

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

Comments

[Максим Тимофеев]

Для начала надо создать массив в котором будут не фигуры, а их вариации. Причем высота отдельно, а ширина отдельно и исходное название отдельно

[Шаров Дмитрий]

сколько фигур и каких фигур есть? есть установленная полезная ценность у фигур?
при такой постановке задачи можно просто сказать что сначала большую саму берем заполняем максимально ими, потом меньше, и в последнюю очередь 1*1

[MassTek]

Максим Тимофеев: не могли бы вы уточнить? Я так понимаю, что необходимо создать три массива. 1) Вариации высот, 2) Вариации ширин и третий?

[MassTek]

Шаров Дмитрий: Полезной ценности у фигур нет, пихать можно как угодно. Важным условием является только возможность поворачивать фигуру 2х1 для лучшей оптимизации. Спасибо за совет, попробую наполнять так

[Максим Тимофеев]

MassTek: один массив

[
[1,2,'1x2'],
[2,1,'1x2'],
[1,1,'1x1'],
[2,2,'2x2'],
]

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

Answer 1

[uvelichitel]

Задача рюкзака вообще NPполная, на PHP будет считаться веками. В вашей частной формулировке задача решается без замысловатых алгоритмов. Считайте эталонной упаковкой - два больших квадрата(их больше не влезет) на которых лежат две палки(больше не влезет). Далее большой квадрат может быть заменен двумя палками, а палка двумя малыми квадратами - так вы получите дерево всех оптимальных решений. Оно небольшое.