Binpackningsproblemet
När du flyttar fyller du den ena kartongen efter den andra och undrar om en smartare ordning hade krävt färre. Det är binpackningsproblemet, och det är ökänt svårt: även datorer hittar det minsta antalet lådor för stora indata bara genom smart sökning. Enkla regler kommer ändå förvånansvärt nära.
Problemet
Givet föremål med storlekar och lådor som rymmer lika mycket var, ska varje föremål läggas i en låda så att ingen låda blir överfull, med så få lådor som möjligt. Storlekarna kan stå för vikter, längder, tidsåtgång eller filstorlekar. Det låter som en gåta för en regnig eftermiddag, men det är NP-svårt: ingen metod är känd som snabbt hittar det minsta antalet lådor för varje indata.
Snabba regler
Next Fit fyller en låda tills nästa föremål inte får plats, börjar sedan en ny låda och ser aldrig tillbaka. First Fit håller alla lådor öppna och lägger varje föremål i den första lådan med plats. Best Fit lägger varje föremål i den fullaste lådan som fortfarande har plats. Alla tre bestämmer sig direkt, vilket är användbart när föremålen kommer ett i taget och måste placeras genast.
Sortera först
Stora föremål är de svåra, eftersom de behöver mycket ledigt utrymme. Om man sorterar föremålen från största till minsta och sedan använder First Fit eller Best Fit, kommer de stora ner medan lådorna fortfarande är tomma, och de små fyller luckorna. First Fit Decreasing använder aldrig mer än 11/9 av det minsta antalet lådor, plus en konstant, mot 1,7 gånger för First Fit på osorterade föremål.
Ett exempel
Ta lådor av storlek 10 och föremålen 2, 3, 2, 1, 3, 4, 5, 6, 7 och 7, som tillsammans blir 40. First Fit lägger 2, 3, 2 och 1 i den första lådan och 3 och 4 i den andra, och sedan behöver 5, 6, 7 och 7 var sin låda: 6 lådor. Sorterat med de största först gör First Fit Decreasing 7 + 3, 7 + 3, 6 + 4 och 5 + 2 + 2 + 1: 4 fulla lådor, precis den undre gränsen 40 / 10 = 4.
Hitta det minsta antalet lådor
För ett litet antal föremål kan det exakta svaret hittas med dynamisk programmering över delmängder: för varje mängd av föremål det minsta antalet lådor och den tommaste sista lådan som rymmer den, uppbyggt från mängderna med ett föremål mindre. Det tar ungefär 2ⁿ·n steg för n föremål. Större instanser löses med branch and bound eller heltalsprogrammering, och den undre gränsen visar hur långt från det bästa en packning som mest kan vara.
Var det används
Att lasta lastbilar och containrar, kapa rör eller pappersrullar från standardlängder med så lite spill som möjligt (kapningsproblemet), placera virtuella maskiner på servrar och lägga filer på diskar är alla binpackningsproblem. I två och tre dimensioner, med kartonger i stället för tal, är problemet ännu svårare.
Ofta ställda frågor
Vad är skillnaden mellan online- och offline-binpackning?
Online måste varje föremål placeras så fort det kommer, utan att man känner till resten; så fungerar Next Fit, First Fit och Best Fit. Offline är alla föremål kända i förväg, så de kan sorteras först, som First Fit Decreasing gör.
Hur nära det bästa kommer First Fit Decreasing?
Den använder högst 11/9 av det minsta antalet lådor plus 6/9 låda, en gräns som György Dósa 2007 bevisade är skarp. På vanliga indata är den oftast optimal eller en låda ifrån.
Är binpackning samma sak som kappsäcksproblemet?
De är besläktade men olika. Kappsäcksproblemet fyller en enda väska med de mest värdefulla föremålen; binpackning lägger alla föremål i så få väskor som möjligt. Exakta lösare för binpackning fungerar ofta genom att lösa kappsäcksliknande problem om och om igen.
Varför tillåter appen bara 12 föremål?
Eftersom det exakta svaret går igenom varje mängd av föremål, och 12 föremål ger redan 4 096 mängder. De snabba reglerna skulle klara tusentals föremål, men det skulle inte ritningen och jämförelsen med det exakta svaret.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova binpackning