bin packing problem revised

0

1

Встречаем, дамы и господа, избитая проблема рюкзака снова с нами.

Даже не сам классический рюкзак, а вариация на тему bin packing.

Итак, имеем стенд. На нем 5 куч. Высота стенда — 1.5 метра.
Имеем 3 вида кубиков: 15см, 18см и 23см.
Задача: независимо от входных данных (кол-ва разных кубиков) аппроксимировать их оптимальное расположение на стендах. Естественно, задействуя как можно меньшее кол-во стендов.

Ссылка

←	Разрыв шаблона про проприетарщину

Отвалился binwalk

→

Это ЛОР должен решить или ты просишь помощи? К целочисленному программированию не сводится?

backburner
(26.05.15 15:12:46 MSK)

Ответ на: комментарий от backburner 26.05.15 15:12:46 MSK

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

~~unt1tled~~ ★★★★
(26.05.15 15:16:46 MSK) автор топика

Ссылка

Ну, например, так:

1. Разделить максимальную высоту на высоту самого высокого кубика. Получится 6 по 23
2. Сделать 5 деревьев с 6 нодами, представляющими высоту максимального кубика.
3. Заполнять снизу вверх biggest first проходя по деревьям и суя 1 кубик за раз в каждое.
4. Когда закончатся большие, перейти к средним, пихать их и оставшееся число переносить на ноду вверх, помечая ноду, в которую суем, как грязную.
5. Затем к самым маленьким.
6. PROFIT??