- Voorwerp dat ingepakt wordt
- Past
- Past niet
Bin-packingprobleem
Dozen in busjes, bestanden op schijven, taken op machines: het bin-packingprobleem vraagt hoe je een lijst voorwerpen in zo weinig mogelijk gelijke bakken krijgt. Er is geen snelle methode bekend die altijd de beste indeling vindt, maar eenvoudige regels komen dicht in de buurt. Kies een regel, loop hem stap voor stap door en vergelijk met het exacte antwoord. Tik op een voorwerp op de plank en tik dan op een bak om het erin te leggen: groene bakken hebben er ruimte voor, en Nieuwe bak opent er nog een. Tik op een voorwerp in een bak om het er weer uit te halen. Pak alle voorwerpen in zo weinig mogelijk bakken in; de ondergrens (het totale gewicht gedeeld door de grootte van de bakken, naar boven afgerond) en het minst mogelijke laten zien hoe dicht je erbij zit, en Minste bakken toont de beste verdeling. Verander de gewichten van de voorwerpen (in kilogram) en de grootte van de bakken in het paneel. De weergave Stap voor stap laat zien hoe de snelle regels inpakken: Next Fit, First Fit of Best Fit, met de voorwerpen in de ingevoerde volgorde of gesorteerd met de grootste eerst, of het exacte antwoord dat dynamisch programmeren vindt. Druk op Afspelen om de voorwerpen in de bakken te zien gaan, of op Stap en Terug om stap voor stap te gaan, en sleep de stapschuif om ergens heen te springen. Als het speelveld geselecteerd is, gaan de pijltjestoetsen een stap verder, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.
Hoe het werkt
- Tik op een voorwerp en dan op een bak met ruimte om het erin te leggen, of op Nieuwe bak om er nog een te openen.
- Probeer zo min mogelijk bakken te gebruiken, of druk op Minste bakken om de beste indeling te zien.
- Open de weergave Stap voor stap, kies een regel en druk op Afspelen om elk voorwerp de bakken te zien proberen.
De regels
Next Fit houdt alleen de laatste bak open: een voorwerp dat daar niet in past, begint een nieuwe bak. First Fit probeert de bakken vanaf de eerste en neemt de eerste met genoeg ruimte. Best Fit probeert elke bak en neemt de volste met genoeg ruimte, zodat er zo weinig mogelijk ruimte ongebruikt blijft. First Fit en Best Fit kunnen de voorwerpen ook eerst van groot naar klein sorteren; dat geeft First Fit Decreasing en Best Fit Decreasing.
Het exacte antwoord
De laatste regel is geen vuistregel: hij vindt het kleinste aantal bakken met dynamisch programmeren over de verzamelingen voorwerpen. Voor elke verzameling voorwerpen onthoudt hij het kleinste aantal bakken waar ze in passen en, onder de indelingen met zoveel bakken, de kleinste vulling van de laatste bak. Een verzameling groeit met één voorwerp tegelijk, dat de laatste bak verder vult of een nieuwe opent. Met n voorwerpen zijn er 2ⁿ verzamelingen; daarom staat de app hoogstens 12 voorwerpen toe. De ondergrens, de totale grootte gedeeld door de grootte van de bakken en naar boven afgerond, laat zien hoe dicht een indeling bij het beste zit.
Veelgestelde vragen
Welke bin-packingregel is het beste?
Van de snelle regels zijn First Fit Decreasing en Best Fit Decreasing het sterkst: ze gebruiken nooit meer dan 11/9 van het kleinste aantal bakken, plus een kleine constante. First Fit en Best Fit op ongesorteerde voorwerpen blijven binnen 1,7 keer het kleinste aantal bakken, en Next Fit binnen 2 keer.
Waarom is bin packing moeilijk?
Beslissen of de voorwerpen in maar twee bakken passen, is al het partitieprobleem, en dat is NP-volledig. Tenzij P = NP vindt dus geen enkele methode voor elke invoer snel het kleinste aantal bakken, en exacte methoden kosten in het slechtste geval exponentiële tijd.
Wat is de ondergrens?
De totale grootte van de voorwerpen gedeeld door de grootte van de bakken, naar boven afgerond. Geen indeling kan minder bakken gebruiken, want de bakken moeten alle voorwerpen bevatten. Vaak haalt de beste indeling die grens, maar niet altijd: drie voorwerpen van grootte 6 met bakken van 10 hebben een ondergrens van 2 en hebben 3 bakken nodig.
Is dit dynamisch programmeren?
Het exacte antwoord wel: het bouwt de beste indeling voor elke verzameling voorwerpen op uit de beste indelingen van kleinere verzamelingen. De snelle regels zijn gretige methoden, die één keer beslissen en nooit terugkijken.
Wordt er iets verstuurd?
Nee. Alles wordt in je browser berekend, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor