Метка «задача о рюкзаке»

Это продолжение поста про оффлайн алгоритмы упаковки.

Суть задачи: имеем полубесконечную полосу — как в тетрисе, только без game over'а, и конечный набор прямоугольников. Данные о прямоугольниках поступают в режиме реального времени; каждый новый прямоугольник необходимо немедленно разместить и больше не двигать с места. Цель — минимизировать общую высоту упакованных прямоугольников.
Это online-вариация задачи об упаковке прямоугольников в полуограниченную полосу (2 Dimensional Strip Packing, 2DSP).

Чуть больше теоретических сведений можно найти в предыдущей статье, а пока, без лишних слов, перейдем к алгоритмам.
Читать полностью »

Сегодня, дорогой Хабр, я расскажу тебе историю о комбинаторной оптимизации.
Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.

От задачи о ранце отпочковалась задача об упаковке в контейнеры (Bin Packing Problem), одной из разновидностей которых является задача двумерной упаковки (2-Dimensional Bin Packing). Снова отбросив несколько вариаций, мы наконец придем к двумерной упаковке в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP). Чувствуете, сколько интересного уже осталось за кадром? Но мы еще не закончили продираться сквозь классификацию. У 2DSP есть два варианта входных данных: когда набор упаковываемых объектов известен заранее (offline-проблема) и когда данные поступают порциями (online-проблема).

В этой статье рассматриваются алгоритмы решения offline-варианта 2DSP. Под катом немного матчасти и много картинок с цветными квадратиками.

В чем, собственно, проблема?

Читать полностью »