- Pakowany przedmiot
- Mieści się
- Nie mieści się
Problem pakowania (bin packing)
Paczki do furgonetek, pliki na dyski, zadania na maszyny: problem pakowania pyta, jak zmieścić listę przedmiotów w jak najmniejszej liczbie jednakowych pojemników. Nie jest znana żadna szybka metoda, która zawsze znajduje najlepsze upakowanie, ale proste reguły są blisko. Wybierz regułę, przejdź ją krok po kroku i porównaj z dokładną odpowiedzią. Dotknij przedmiotu na półce, a potem dotknij pojemnika, aby go do niego włożyć: zielone pojemniki mają na niego miejsce, a Nowy pojemnik otwiera kolejny. Dotknij przedmiotu w pojemniku, aby go z powrotem wyjąć. Spakuj wszystkie przedmioty do jak najmniejszej liczby pojemników; dolne ograniczenie (łączna waga podzielona przez rozmiar pojemnika, zaokrąglona w górę) i minimalna liczba pokazują, jak blisko jesteś, a Najmniej pojemników pokazuje najlepsze spakowanie. Zmień wagi przedmiotów (w kilogramach) i rozmiar pojemnika w panelu. Widok Krok po kroku pokazuje, jak pakują szybkie reguły: Next Fit, First Fit lub Best Fit, dla przedmiotów we wpisanej kolejności lub posortowanych od największego, albo dokładną odpowiedź znalezioną przez programowanie dynamiczne. Naciśnij Odtwórz, aby zobaczyć, jak przedmioty trafiają do pojemników, albo Krok i Wstecz, aby przechodzić krok po kroku, i przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Gdy plansza jest zaznaczona, strzałki przechodzą o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.
Jak to działa
- Stuknij przedmiot, a potem pojemnik z miejscem, aby go tam włożyć, albo Nowy pojemnik, aby otworzyć kolejny.
- Spróbuj użyć jak najmniej pojemników albo naciśnij Najmniej pojemników, aby zobaczyć najlepsze ułożenie.
- Otwórz widok Krok po kroku, wybierz regułę i naciśnij Odtwórz, aby zobaczyć, jak każdy przedmiot próbuje kolejnych pojemników.
Reguły
Next Fit trzyma otwarty tylko ostatni pojemnik: przedmiot, który się w nim nie mieści, zaczyna nowy pojemnik. First Fit próbuje pojemników od pierwszego i wybiera pierwszy z wolnym miejscem. Best Fit próbuje każdego pojemnika i wybiera najpełniejszy z wolnym miejscem, więc zostawia najmniej niewykorzystanego miejsca. First Fit i Best Fit mogą też najpierw posortować przedmioty od największego do najmniejszego; tak powstają First Fit Decreasing i Best Fit Decreasing.
Dokładna odpowiedź
Ostatnia reguła nie jest regułą na oko: znajduje najmniejszą liczbę pojemników przez programowanie dynamiczne po zbiorach przedmiotów. Dla każdego zbioru przedmiotów zapamiętuje najmniejszą liczbę pojemników, które je pomieszczą, a spośród upakowań z taką liczbą pojemników najmniejsze zapełnienie ostatniego pojemnika. Zbiór rośnie o jeden przedmiot naraz, który albo dopełnia ostatni pojemnik, albo otwiera nowy. Dla n przedmiotów jest 2ⁿ zbiorów, dlatego aplikacja pozwala na najwyżej 12 przedmiotów. Dolne ograniczenie, czyli łączny rozmiar podzielony przez rozmiar pojemnika i zaokrąglony w górę, pokazuje, jak blisko najlepszego jest dane upakowanie.
Często zadawane pytania
Która reguła pakowania jest najlepsza?
Spośród szybkich reguł najsilniejsze są First Fit Decreasing i Best Fit Decreasing: nigdy nie używają więcej niż 11/9 najmniejszej liczby pojemników plus mała stała. First Fit i Best Fit na nieposortowanych przedmiotach mieszczą się w 1,7 raza najmniejszej liczby pojemników, a Next Fit w 2 razach.
Dlaczego problem pakowania jest trudny?
Już rozstrzygnięcie, czy przedmioty zmieszczą się w zaledwie dwóch pojemnikach, to problem podziału zbioru, który jest NP-zupełny. Jeśli więc nie jest prawdą, że P = NP, żadna metoda nie znajduje szybko najmniejszej liczby pojemników dla każdych danych, a metody dokładne w najgorszym przypadku działają w czasie wykładniczym.
Czym jest dolne ograniczenie?
To łączny rozmiar przedmiotów podzielony przez rozmiar pojemnika, zaokrąglony w górę. Żadne upakowanie nie może użyć mniej pojemników, bo pojemniki muszą pomieścić wszystkie przedmioty. Często najlepsze upakowanie je osiąga, ale nie zawsze: trzy przedmioty o rozmiarze 6 przy pojemnikach o rozmiarze 10 mają dolne ograniczenie 2, a potrzebują 3 pojemników.
Czy to jest programowanie dynamiczne?
Dokładna odpowiedź tak: buduje najlepsze upakowanie każdego zbioru przedmiotów z najlepszych upakowań mniejszych zbiorów. Szybkie reguły to metody zachłanne, które decydują raz i nigdy nie wracają.
Czy cokolwiek jest gdzieś wysyłane?
Nie. Wszystko jest liczone w Twojej przeglądarce, a Twoje ostatnie ustawienia zostają w pamięci lokalnej tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora