- Genstand, der pakkes
- Passer
- Passer ikke
Bin packing-problemet
Flyttekasser i varevogne, filer på diske, opgaver på maskiner: bin packing-problemet spørger, hvordan man får en liste af genstande ned i så få ens kasser som muligt. Der kendes ingen hurtig metode, som altid finder den bedste pakning, men enkle regler kommer tæt på. Vælg en regel, gå den igennem trin for trin, og sammenlign med det eksakte svar. Tryk på en genstand på hylden, og tryk derefter på en kasse for at lægge den i: grønne kasser har plads til den, og Ny kasse åbner en til. Tryk på en genstand i en kasse for at tage den ud igen. Pak alle genstande i så få kasser som muligt; den nedre grænse (den samlede vægt delt med kassestørrelsen, rundet op) og færrest mulige viser, hvor tæt du er på, og Færrest kasser viser den bedste pakning. Ret genstandenes vægt (i kilogram) og kassestørrelsen i panelet. Visningen Trin for trin viser, hvordan de hurtige regler pakker: Next Fit, First Fit eller Best Fit, med genstandene i den indtastede rækkefølge eller sorteret med de største først, eller det eksakte svar fundet med dynamisk programmering. Tryk på Afspil for at se genstandene komme i kasserne, eller på Trin og Tilbage for at gå ét trin ad gangen, og træk i trinskyderen for at springe hvorhen du vil. Når spillepladen er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.
Sådan virker det
- Tryk på en genstand og derefter på en kasse med plads for at lægge den i, eller på Ny kasse for at åbne en ny.
- Prøv at bruge så få kasser som muligt, eller tryk på Færrest kasser for at se den bedste pakning.
- Åbn visningen Trin for trin, vælg en regel, og tryk på Afspil for at se hver genstand prøve kasserne.
Reglerne
Next Fit holder kun den sidste kasse åben: en genstand, der ikke passer i den, starter en ny kasse. First Fit prøver kasserne fra den første og tager den første med plads. Best Fit prøver alle kasser og tager den fyldeste med plads, så mindst mulig plads står ubrugt. First Fit og Best Fit kan også først sortere genstandene fra største til mindste, hvilket giver First Fit Decreasing og Best Fit Decreasing.
Det eksakte svar
Den sidste regel er ikke en tommelfingerregel: den finder det mindste antal kasser med dynamisk programmering over mængderne af genstande. For hver mængde af genstande gemmer den det mindste antal kasser, der kan rumme dem, og blandt pakninger med så mange kasser den mindste fyldning i den sidste kasse. En mængde vokser én genstand ad gangen, som enten fylder den sidste kasse op eller åbner en ny. Med n genstande er der 2ⁿ mængder, og derfor tillader appen højst 12 genstande. Den nedre grænse, altså den samlede størrelse divideret med kassestørrelsen og rundet op, viser, hvor tæt en pakning er på det bedste.
Ofte stillede spørgsmål
Hvilken bin packing-regel er bedst?
Af de hurtige regler er First Fit Decreasing og Best Fit Decreasing de stærkeste: de bruger aldrig mere end 11/9 af det mindste antal kasser plus en lille konstant. First Fit og Best Fit på usorterede genstande holder sig inden for 1,7 gange det mindste antal kasser, og Next Fit inden for 2 gange.
Hvorfor er bin packing svært?
At afgøre, om genstandene kan være i kun to kasser, er allerede partitionsproblemet, som er NP-komplet. Så medmindre P = NP, finder ingen metode hurtigt det mindste antal kasser for alle input, og eksakte metoder tager eksponentiel tid i værste fald.
Hvad er den nedre grænse?
Genstandenes samlede størrelse divideret med kassestørrelsen, rundet op. Ingen pakning kan bruge færre kasser, for kasserne skal rumme alle genstandene. Ofte når den bedste pakning den, men ikke altid: tre genstande med størrelsen 6 og kasser på 10 har en nedre grænse på 2 og kræver 3 kasser.
Er det her dynamisk programmering?
Det eksakte svar er: det bygger den bedste pakning for hver mængde af genstande ud fra de bedste pakninger af mindre mængder. De hurtige regler er grådige metoder, som beslutter én gang og aldrig ser tilbage.
Bliver noget sendt nogen steder hen?
Nej. Alt beregnes i din browser, og dine seneste indstillinger bliver i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor