LINUX.ORG.RU
Форум — Talks  

bin packing problem revised

 , ,


0

1

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

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

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

★★★★

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

backburner
()
Ответ на: комментарий от backburner

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

unt1tled ★★★★
() автор топика

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

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

unt1tled ★★★★
() автор топика
Последнее исправление: unt1tled (всего исправлений: 2)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Talks