Problem pakowania

Przy przeprowadzce pakujesz jeden karton za drugim i zastanawiasz się, czy przy sprytniejszej kolejności wystarczyłoby mniej. To jest problem pakowania i słynie z tego, że jest trudny: nawet komputery znajdują najmniejszą liczbę pojemników dla dużych danych tylko dzięki sprytnemu przeszukiwaniu. Proste reguły są jednak zaskakująco blisko.

Pojemniki o tej samej wysokości wypełnione ułożonymi jeden na drugim kolorowymi przedmiotami różnej wielkości, a nad nimi czekają kolejne przedmioty
Pojemniki o tej samej wysokości wypełnione ułożonymi jeden na drugim kolorowymi przedmiotami różnej wielkości, a nad nimi czekają kolejne przedmioty

Problem

Mamy przedmioty o danych rozmiarach i pojemniki, z których każdy mieści tyle samo. Trzeba włożyć każdy przedmiot do pojemnika tak, by żaden pojemnik się nie przepełnił, używając jak najmniej pojemników. Rozmiary mogą oznaczać wagi, długości, czasy trwania albo rozmiary plików. Brzmi jak łamigłówka na deszczowe popołudnie, ale problem jest NP-trudny: nie jest znana żadna metoda, która szybko znajduje najmniejszą liczbę pojemników dla każdych danych.

Szybkie reguły

Next Fit zapełnia jeden pojemnik, dopóki następny przedmiot się mieści, potem zaczyna nowy pojemnik i nigdy nie wraca. First Fit trzyma wszystkie pojemniki otwarte i wkłada każdy przedmiot do pierwszego pojemnika z wolnym miejscem. Best Fit wkłada każdy przedmiot do najpełniejszego pojemnika, w którym jest jeszcze miejsce. Wszystkie trzy decydują od razu, co jest przydatne, gdy przedmioty przychodzą pojedynczo i trzeba je od razu umieścić.

Najpierw posortuj

Duże przedmioty są tymi trudnymi, bo potrzebują dużo wolnego miejsca. Jeśli posortujesz przedmioty od największego do najmniejszego, a potem użyjesz First Fit albo Best Fit, duże trafią do pojemników, póki te są jeszcze puste, a małe wypełnią luki. First Fit Decreasing nigdy nie używa więcej niż 11/9 najmniejszej liczby pojemników plus stała, wobec 1,7 raza dla First Fit na nieposortowanych przedmiotach.

Przykład

Weź pojemniki o rozmiarze 10 i przedmioty 2, 3, 2, 1, 3, 4, 5, 6, 7 i 7, które razem dają 40. First Fit wkłada 2, 3, 2 i 1 do pierwszego pojemnika, a 3 i 4 do drugiego, a potem 5, 6, 7 i 7 potrzebują każdy osobnego pojemnika: 6 pojemników. Po posortowaniu od największego First Fit Decreasing tworzy 7 + 3, 7 + 3, 6 + 4 oraz 5 + 2 + 2 + 1: 4 pełne pojemniki, dokładnie tyle, ile dolne ograniczenie 40 / 10 = 4.

Szukanie najmniejszej liczby pojemników

Dla niewielu przedmiotów dokładną odpowiedź można znaleźć przez programowanie dynamiczne po podzbiorach: dla każdego zbioru przedmiotów najmniejszą liczbę pojemników i najmniej zapełniony ostatni pojemnik, które go mieszczą, zbudowane ze zbiorów o jeden przedmiot mniejszych. Zajmuje to około 2ⁿ·n kroków dla n przedmiotów. Większe przypadki rozwiązuje się metodą podziału i ograniczeń albo programowaniem całkowitoliczbowym, a dolne ograniczenie mówi, jak daleko od najlepszego może być upakowanie.

Gdzie się go stosuje

Załadunek ciężarówek i kontenerów, cięcie rur lub rolek papieru ze standardowych długości przy jak najmniejszych odpadach (problem rozkroju), rozmieszczanie maszyn wirtualnych na serwerach i zapisywanie plików na dyskach to wszystko problemy pakowania. W dwóch i trzech wymiarach, z pudełkami zamiast liczb, problem jest jeszcze trudniejszy.

Często zadawane pytania

Czym różni się pakowanie online od offline?

Online każdy przedmiot trzeba umieścić od razu, gdy się pojawi, bez znajomości pozostałych; tak działają Next Fit, First Fit i Best Fit. Offline wszystkie przedmioty są znane z góry, więc można je najpierw posortować, jak robi to First Fit Decreasing.

Jak blisko najlepszego wyniku jest First Fit Decreasing?

Używa najwyżej 11/9 najmniejszej liczby pojemników plus 6/9 pojemnika; György Dósa udowodnił w 2007 roku, że to ograniczenie jest dokładne. Dla typowych danych wynik jest zwykle optymalny albo o jeden pojemnik gorszy.

Czy problem pakowania to to samo co problem plecakowy?

Są powiązane, ale różne. Problem plecakowy wypełnia jeden plecak najcenniejszymi przedmiotami; problem pakowania wkłada każdy przedmiot do jak najmniejszej liczby plecaków. Dokładne algorytmy dla problemu pakowania często działają, rozwiązując raz za razem problemy podobne do plecakowego.

Dlaczego aplikacja pozwala tylko na 12 przedmiotów?

Bo dokładna odpowiedź przegląda każdy zbiór przedmiotów, a 12 przedmiotów daje już 4096 zbiorów. Szybkie reguły poradziłyby sobie z tysiącami przedmiotów, ale rysunek i porównanie z dokładną odpowiedzią już nie.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj problem pakowania