- Obiect în curs de împachetare
- Încape
- Nu încape
Problema împachetării (bin packing)
Cutii în dube, fișiere pe discuri, sarcini pe mașini: problema împachetării întreabă cum se pot pune obiectele dintr-o listă în cât mai puține containere egale. Nu se cunoaște nicio metodă rapidă care să găsească mereu cea mai bună împachetare, dar regulile simple se apropie mult. Alegeți o regulă, parcurgeți-o pas cu pas și comparați cu răspunsul exact. Atingeți un obiect de pe raft, apoi atingeți un container pentru a-l pune în el: containerele verzi au loc pentru el, iar Container nou deschide încă unul. Atingeți un obiect dintr-un container pentru a-l scoate din nou. Împachetați toate obiectele în cât mai puține containere; limita inferioară (greutatea totală împărțită la dimensiunea containerului, rotunjită în sus) și minimul posibil arată cât de aproape sunteți, iar Cele mai puține containere arată cea mai bună împachetare. Schimbați greutățile obiectelor (în kilograme) și dimensiunea containerului în panou. Vizualizarea Pas cu pas arată cum împachetează regulile rapide: Next Fit, First Fit sau Best Fit, cu obiectele în ordinea introdusă sau sortate de la cel mai mare, ori răspunsul exact găsit prin programare dinamică. Apăsați Redare pentru a vedea cum intră obiectele în containere, sau Pas și Înapoi pentru a merge câte un pas, și trageți de cursorul pașilor pentru a sări oriunde. Cu tabla selectată, tastele săgeți avansează câte un pas, bara de spațiu pornește și întrerupe redarea, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Atingeți un obiect, apoi un container cu loc ca să-l puneți acolo, sau Container nou ca să deschideți altul.
- Încercați să folosiți cât mai puține containere sau apăsați Cele mai puține containere ca să vedeți cea mai bună împachetare.
- Deschideți vizualizarea Pas cu pas, alegeți o regulă și apăsați Redare ca să vedeți cum fiecare obiect încearcă containerele.
Regulile
Next Fit ține deschis doar ultimul container: un obiect care nu încape acolo începe un container nou. First Fit încearcă containerele de la primul și îl alege pe primul care are loc. Best Fit încearcă toate containerele și îl alege pe cel mai plin care are loc, lăsând cât mai puțin spațiu nefolosit. First Fit și Best Fit pot și să sorteze mai întâi obiectele de la cel mai mare la cel mai mic, ceea ce dă First Fit Decreasing și Best Fit Decreasing.
Răspunsul exact
Ultima regulă nu este o regulă aproximativă: găsește cel mai mic număr de containere prin programare dinamică pe mulțimile de obiecte. Pentru fiecare mulțime de obiecte păstrează cel mai mic număr de containere care le cuprind și, dintre împachetările cu atâtea containere, cea mai mică încărcare a ultimului container. O mulțime crește cu câte un obiect, care fie completează ultimul container, fie deschide unul nou. Cu n obiecte există 2ⁿ mulțimi, de aceea aplicația permite cel mult 12 obiecte. Limita inferioară, adică dimensiunea totală împărțită la dimensiunea containerului și rotunjită în sus, arată cât de aproape de cea mai bună este o împachetare.
Întrebări frecvente
Care regulă de împachetare este cea mai bună?
Dintre regulile rapide, First Fit Decreasing și Best Fit Decreasing sunt cele mai puternice: nu folosesc niciodată mai mult de 11/9 din numărul minim de containere, plus o mică constantă. First Fit și Best Fit pe obiecte nesortate rămân sub 1,7 ori numărul minim de containere, iar Next Fit sub 2 ori.
De ce este grea problema împachetării?
A decide dacă obiectele încap în doar două containere este deja problema partiției, care este NP-completă. Așadar, dacă nu cumva P = NP, nicio metodă nu găsește rapid cel mai mic număr de containere pentru orice date, iar metodele exacte au nevoie de timp exponențial în cel mai rău caz.
Ce este limita inferioară?
Dimensiunea totală a obiectelor împărțită la dimensiunea containerului, rotunjită în sus. Nicio împachetare nu poate folosi mai puține containere, pentru că acestea trebuie să cuprindă toate obiectele. Adesea cea mai bună împachetare o atinge, dar nu întotdeauna: trei obiecte de dimensiune 6 cu containere de 10 au limita inferioară 2 și au nevoie de 3 containere.
Este aceasta programare dinamică?
Răspunsul exact da: construiește cea mai bună împachetare pentru fiecare mulțime de obiecte din cele mai bune împachetări ale mulțimilor mai mici. Regulile rapide sunt metode greedy, care decid o singură dată și nu se mai întorc niciodată.
Se trimite ceva undeva?
Nu. Totul se calculează în browserul dumneavoastră, iar ultimele setări rămân în spațiul de stocare local al acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor