- Föremål som packas
- Får plats
- Får inte plats
Binpackningsproblemet
Kartonger i skåpbilar, filer på diskar, jobb på maskiner: binpackningsproblemet handlar om hur man får in en lista med föremål i så få lika stora lådor som möjligt. Ingen snabb metod är känd som alltid hittar den bästa packningen, men enkla regler kommer nära. Välj en regel, stega igenom den och jämför med det exakta svaret. Tryck på ett föremål på hyllan och tryck sedan på en låda för att lägga det i den: gröna lådor har plats för det, och Ny låda öppnar en till. Tryck på ett föremål i en låda för att ta ut det igen. Packa alla föremål i så få lådor som möjligt; den undre gränsen (den totala vikten delad med lådstorleken, avrundad uppåt) och minsta möjliga visar hur nära du är, och Minst antal lådor visar den bästa packningen. Ändra föremålens vikter (i kilogram) och lådstorleken i panelen. Vyn Steg för steg visar hur de snabba reglerna packar: Next Fit, First Fit eller Best Fit, med föremålen i inskriven ordning eller sorterade med de största först, eller det exakta svaret som dynamisk programmering hittar. Tryck på Spela för att se föremålen hamna i lådorna, eller på Steg och Bakåt för att gå ett steg i taget, och dra i stegreglaget för att hoppa vart som helst. När spelplanen är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Tryck på ett föremål och sedan på en låda med plats för att lägga det där, eller på Ny låda för att öppna en till.
- Försök använda så få lådor som möjligt, eller tryck på Minst antal lådor för att se den bästa packningen.
- Öppna vyn Steg för steg, välj en regel och tryck på Spela för att se varje föremål prova lådorna.
Reglerna
Next Fit håller bara den sista lådan öppen: ett föremål som inte får plats där börjar en ny låda. First Fit provar lådorna från den första och tar den första med plats. Best Fit provar varje låda och tar den fullaste med plats, så att minst utrymme blir oanvänt. First Fit och Best Fit kan också först sortera föremålen från största till minsta, vilket ger First Fit Decreasing och Best Fit Decreasing.
Det exakta svaret
Den sista regeln är ingen tumregel: den hittar det minsta antalet lådor med dynamisk programmering över mängderna av föremål. För varje mängd av föremål sparar den det minsta antalet lådor som rymmer dem och, bland packningar med så många lådor, den minsta fyllnaden i den sista lådan. En mängd växer med ett föremål i taget, som antingen fyller på den sista lådan eller öppnar en ny. Med n föremål finns det 2ⁿ mängder, och därför tillåter appen högst 12 föremål. Den undre gränsen, alltså den totala storleken delad med lådstorleken och avrundad uppåt, visar hur nära det bästa en packning är.
Ofta ställda frågor
Vilken binpackningsregel är bäst?
Av de snabba reglerna är First Fit Decreasing och Best Fit Decreasing starkast: de använder aldrig mer än 11/9 av det minsta antalet lådor, plus en liten konstant. First Fit och Best Fit på osorterade föremål håller sig inom 1,7 gånger det minsta antalet lådor, och Next Fit inom 2 gånger.
Varför är binpackning svårt?
Att avgöra om föremålen får plats i bara två lådor är redan partitionsproblemet, som är NP-fullständigt. Så om inte P = NP finns det ingen metod som snabbt hittar det minsta antalet lådor för varje indata, och exakta metoder tar exponentiell tid i värsta fall.
Vad är den undre gränsen?
Föremålens totala storlek delad med lådstorleken, avrundad uppåt. Ingen packning kan använda färre lådor, eftersom lådorna måste rymma alla föremål. Ofta når den bästa packningen gränsen, men inte alltid: tre föremål av storlek 6 med lådor på 10 har en undre gräns på 2 och behöver 3 lådor.
Är det här dynamisk programmering?
Det exakta svaret är det: det bygger den bästa packningen för varje mängd av föremål från de bästa packningarna av mindre mängder. De snabba reglerna är giriga metoder, som bestämmer sig en gång och aldrig ser tillbaka.
Skickas något någonstans?
Nej. Allt räknas ut i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor