Aantal rollen in een doos.

[Verwijderd]

Ik zou moeten berekenen hoeveel rollen van verchillende diameter er in een bepaalde doos passen.

Dit terug gebracht naar een iets eenvoudiger model: hoeveel cirkels met verschillende diameter krijg ik in een rechthoek.

Na wat gezocht te hebben kwam ik op het circle packing probleem uit, maar dat gaat ervan uit dat je weet hoe de cirkels elkaar raken (hoeveel buren een gegeven cirkel heeft). En berekend dan de stralen van de cirkels die aan dit model voldoen...

Dat is dus bij mijn probleem niet gegeven, ik weet de stralen en zoek dus eigenlijk het bijbehorende model... weet iemand een nbaam voor dit probleem?

Of zoek ik het te ver en is er een simpele methode om te berekenen hoeveel cirkels ik in een rechthoek krijg?
Hoogst waarschijnlijk is er geen optimale oplossing, maar iets suboptmaal zou ons al heel ver vooruit helpen.

[Confusion]

"Packing problem"

[jwkempeneers]

Als je de diameter van zo een rol hebt en je weet de langste zijde van de rechthoek, dan doe je toch gewoon de lengte van de rechthoek delen door de diameter van de rol? Dan weet je hoeveel er in de lengte passen. Doe dit hetzelfde met de korte zijde van de rechthoek en vermenigvuldig de uitkomsten met elkaar, dan weet je hoeveel rollen in een rechthoek passen.

Edit: Sorry, ik had over het hoofd gezien dat je verschillende diameters had.

[ Voor 10% gewijzigd door jwkempeneers op 12-11-2007 15:21 ]

[bangkirai]

Ga het gewoon is tekenen in een cad programma?
Klinkt flauw, maar geeft soms sneller inzicht, dan het uit te rekenen.

[Technicality]

jwkempeneers schreef op maandag 12 november 2007 @ 15:20:
Als je de diameter van zo een rol hebt en je weet de langste zijde van de rechthoek, dan doe je toch gewoon de lengte van de rechthoek delen door de diameter van de rol? Dan weet je hoeveel er in de lengte passen. Doe dit hetzelfde met de korte zijde van de rechthoek en vermenigvuldig de uitkomsten met elkaar, dan weet je hoeveel rollen in een rechthoek passen.

Edit: Sorry, ik had over het hoofd gezien dat je verschillende diameters had.

Dus jij stapelt je sinaasappels ook altijd recht?

[Verwijderd]

Tekenen had ik al aan gedacht, maar daar is nog geen algoritme of iets dergelijks uitgekomen helaas.

[josjojo]

Zeer interessant probleem. Op Wikipedia (Packing problem) staat er wel iets over geschreven, maar ik zag niet direct een oplossing voor jouw probleem. Mijn gevoel zegt dat het algoritmisch op te lossen zou moeten zijn. Er zit namelijk veel structuur in.

[bangkirai]

http://www.packomania.com/

Ben bang, dat het niet een simpel iets is, kwam deze link toevallig tegen.

Als je wel een simpel algoritme vind, zou ik er maar gelijk patent opvragen, kun je best wel rijk mee worden...

[ Voor 35% gewijzigd door bangkirai op 13-11-2007 18:40 ]

[Henri]

Een cirkel geeft verpakt even veel ruimte als een vierkant toch? (exclusief heel hard proppen).
Dus diameter is lengte/breedte vierkant dan is het toch makkelijk te plaatsen hoeveel erin kunnen of zit ik er mijlen naast? (denk aan een doos met wc papier, er past geen tweede rol naast binnen de maat van een vierkant met dezelfde breedte/lengte als de diameter van een cirkel)? Enige uitzondering is steensverband maar daar win je volgens mij juist geen ruimte mee?

[Grijze Vos]

Henri schreef op dinsdag 13 november 2007 @ 19:24:
Een cirkel geeft verpakt even veel ruimte als een vierkant toch? (exclusief heel hard proppen).
Dus diameter is lengte/breedte vierkant dan is het toch makkelijk te plaatsen hoeveel erin kunnen of zit ik er mijlen naast? (denk aan een doos met wc papier, er past geen tweede rol naast binnen de maat van een vierkant met dezelfde breedte/lengte als de diameter van een cirkel)? Enige uitzondering is steensverband maar daar win je volgens mij juist geen ruimte mee?

Euhm, je hebt dan 4r² - πr² ruimte die je niet gebruikt. In die ruimte kun je weer een deel van een andere rol kwijt.

[Sick Nick]

Ik zou een raster opstellen wat je doos voorstelt en dan de rollen als punten op dat raster invullen. Dan de combinaties proberen, per combi bijhouden hoeveel niet-ingevulde punten je hebt. Dat minimaliseren en je hebt je optimale indeling.

[Verwijderd]

Verwijderd schreef op maandag 12 november 2007 @ 15:10:
Ik zou moeten berekenen hoeveel rollen van verchillende diameter er in een bepaalde doos passen.

Dit terug gebracht naar een iets eenvoudiger model: hoeveel cirkels met verschillende diameter krijg ik in een rechthoek.. . . . . .

Het antwoord oneindig veel.

De clue is dat de rollen verschillende diameters hebben en wat deze diameters zijn niet is gegeven (tenzij ik slordig ben geweest en de informatie over de gegeven diameters niet gezien heb).

De ruimten tussen de cirkels kan je opvullen met steeds kleinere cirkels totdat je 100% opvulling van de loze ruimte krijgt. In dat geval kan je de cirkels met limiet -------> 0 als diameter gebruiken en dan kan je er een willekeurig groot aantal in de loze ruimten plaatsen. Het aantal wordt dan in de limiet oneindig groot. . .?

Even proberen te bewijzen

1. In een vierkant is de loze ruimte X=d²*(4-pi) als je met 4 cirkels begint
2. Deze loze ruimte >0
3. In X>0 passen N getallen die oppervlakten de cirkels weergeven zodat de som Ni in de limiet gelijk is aan X. Dit lijkt me een vanzelfsprekende oplossing

Je kan allerlei verzamelingen bedenken die het zelfde antwoord i------>∞ geven. . .de diameters hoeven niet aan een specifieke serie te voldoen. Je kan bijvoorbeeld beginnen met cirkels die de loze ruimte opvullen als ware het "bakmeel" cirkels en dan steeds fijner "bakmeel" nemen om de overblijvende ruimte op te vullen.

[Punksmurf]

Maar Vortex2, als je uitgaat van oneindig kleine circels hoef je niet eens moeilijk te gaan doen met het inpassen in de loze ruimte tussen de circels. Al stapel je ze dan gewoon naast elkaar (als ware het vierkanten) dan kan je er nog oneindig veel in kwijt.
Sowieso is ook het formaat van de rechthoek niet gegeven, dus kan je net zo goed uitgaan van een oneindig grote (of oneindig kleine!) rechthoek. Aan dit soort aannames heb je dus duidelijk helemaal niets.

Ik denk ook niet dat TS daadwerkelijk oneindig kleine rollen in een oneindig grote doos wil steken . Het gaat gewoon om een algorithme waar je een bepaalde rechthoek insteekt en een array met diameters en dat dan bepaald hoe je die in zo min mogelijk rechtoeken kan inpassen.

Niet dat ik daar nu een briljante ingeving voor heb, helaas.

[Verwijderd]

Punksmurf schreef op woensdag 14 november 2007 @ 00:35:
Maar Vortex2, als je uitgaat van oneindig kleine circels hoef je niet eens moeilijk te gaan doen met het inpassen in de loze ruimte tussen de circels. Al stapel je ze dan gewoon naast elkaar (als ware het vierkanten) dan kan je er nog oneindig veel in kwijt.
Sowieso is ook het formaat van de rechthoek niet gegeven, dus kan je net zo goed uitgaan van een oneindig grote (of oneindig kleine!) rechthoek. Aan dit soort aannames heb je dus duidelijk helemaal niets.

Ik denk ook niet dat TS daadwerkelijk oneindig kleine rollen in een oneindig grote doos wil steken . Het gaat gewoon om een algorithme waar je een bepaalde rechthoek insteekt en een array met diameters en dat dan bepaald hoe je die in zo min mogelijk rechtoeken kan inpassen.

Niet dat ik daar nu een briljante ingeving voor heb, helaas.

Ik snap wel wat je bedoelt maar TS zou bij voorbaat de vverschillende diameters hebben moeten definieren. . dacht ik. Ik zie daar ook een probleem:

Als je met een gedefinieerde rechthoek begint (axb) en je gaat willekeurig verschillende diameters opnoemen dan ben je er nog niet als je geen extra randvoorwaarden geeft.

Als je het aantal rollen van elke diameter vastlegt zie ik meerdere oplossingen voor het vraagstuk. TS vraagt niet voor een maximaal aantal maar het aantal verschillende diameters in een bepaalde doos. Ik veronderstelde daaruit dat er verschillende diameters in de doos moesten zitten!

Je hoeft trouwens niet een oneindig grote doos te nemen om een oneindig aantal rollen er in te kunnen passen. In een willekeurig kleine doos passen ook een oneindig aantal cirkels

Waarschijnlijk bedoelde TS dat er in een gegeven doos een aantal cirkels van gelijke diameter zouden passen en dat hij dan het zelfde zou doen met andere diameters maar ook weer allemaal gelijk. Je kan dan eindeloos de cirkels kleiner maken en in een willekeurige doos, in de limiet, de diameter naar nul laten gaan en dan gaat het aantal naar oneindig. Ik had niet deze bedoeling er in gelezen

Maar met deze oneindige reeks oplossingen krijg je geen 100% vulling. Mijn oplossing is dus wezenlijk anders omdat de vulling 100% wordt.

Ik vond de oneindige limiet oplossing wel leuk omdat je dan met cirkels waarvan de diameter in de limiet nul is toch een 100% vulling kan krijgen.

[Verwijderd]

bangkirai schreef op dinsdag 13 november 2007 @ 02:39:
Ga het gewoon is tekenen in een cad programma?
Klinkt flauw, maar geeft soms sneller inzicht, dan het uit te rekenen.

Ik denk zelf dat je met een papiertje, een geo en een passer toch echt een eind komt hoor... voor iedereen te doen zonder CAD-cursus

[bangkirai]

Hehe:

Vind het makkelijk om ff cad programmaatje te downloaden als ik het niet meer heb, dan het hele huis overhoop te halen om passer te vinden

Ja ok, potlood met touwtje kan ook...

[Verwijderd]

bangkirai schreef op woensdag 14 november 2007 @ 12:40:

Ja ok, potlood met touwtje kan ook...

Echte tweakert dus

[Verwijderd]

Het lag even stil voor wat anders, maar hier toch even op inpikken, dat is allemaal correct en theoretisch waar, maar ik heb wel degelijk n aantal diameters gegeven die verpakt moeten worden...

Ondertussen ben ik niet veel verder gekomen, maar ik vermoed dat ik het als volgt ga oplossen:
Bereken de totale opervlakte van de cirkels, pas een "foutcorrectie" toe, en kijk hoeveel er in de doos passen.
De foutcorrectie moet dan nog wel proefondervindelijk bepaald worden, maw, moeten we gaan meten hoeveel "verlies" er gemiddeld is bij het inladen van een doos.

Verwijderd schreef op woensdag 14 november 2007 @ 03:08:
[...]


Ik snap wel wat je bedoelt maar TS zou bij voorbaat de vverschillende diameters hebben moeten definieren. . dacht ik. Ik zie daar ook een probleem:

Als je met een gedefinieerde rechthoek begint (axb) en je gaat willekeurig verschillende diameters opnoemen dan ben je er nog niet als je geen extra randvoorwaarden geeft.

Als je het aantal rollen van elke diameter vastlegt zie ik meerdere oplossingen voor het vraagstuk. TS vraagt niet voor een maximaal aantal maar het aantal verschillende diameters in een bepaalde doos. Ik veronderstelde daaruit dat er verschillende diameters in de doos moesten zitten!

Je hoeft trouwens niet een oneindig grote doos te nemen om een oneindig aantal rollen er in te kunnen passen. In een willekeurig kleine doos passen ook een oneindig aantal cirkels

Waarschijnlijk bedoelde TS dat er in een gegeven doos een aantal cirkels van gelijke diameter zouden passen en dat hij dan het zelfde zou doen met andere diameters maar ook weer allemaal gelijk. Je kan dan eindeloos de cirkels kleiner maken en in een willekeurige doos, in de limiet, de diameter naar nul laten gaan en dan gaat het aantal naar oneindig. Ik had niet deze bedoeling er in gelezen

Maar met deze oneindige reeks oplossingen krijg je geen 100% vulling. Mijn oplossing is dus wezenlijk anders omdat de vulling 100% wordt.

Ik vond de oneindige limiet oplossing wel leuk omdat je dan met cirkels waarvan de diameter in de limiet nul is toch een 100% vulling kan krijgen.

[GeeBee]

Verwijderd schreef op woensdag 28 november 2007 @ 22:50:
Het lag even stil voor wat anders, maar hier toch even op inpikken, dat is allemaal correct en theoretisch waar, maar ik heb wel degelijk n aantal diameters gegeven die verpakt moeten worden...
[...]

Als je ons dan even vertelt welke diameters dat zijn, dan kunnen we meedenken.
Ik heb ze niet kunnen lezen in dit topic...

[KopjeThee]

Dit op zich wel een leuke opgave voor een nieuwe programming contest, lijkt mij?

[Verwijderd]

Om weer even verder te gaan op de stelling van Vortex2:
Een doos raakt helemaal niet voller als je er oneindig kleine rollen in gooit. Er passen dus wel oneindig rollen in, maar je krijgt nooit een 100% volle doos.

[Verwijderd]

Verwijderd schreef op zaterdag 01 december 2007 @ 23:20:
Om weer even verder te gaan op de stelling van Vortex2:
Een doos raakt helemaal niet voller als je er oneindig kleine rollen in gooit. Er passen dus wel oneindig rollen in, maar je krijgt nooit een 100% volle doos.

Als je een aantal cilinders tegen elkaar plaatst zit er een loze ruimte tussen. In deze loze ruimte plaats je weer cilinders. . .de loze ruimte wordt opgevuld met een kleine loze ruimte die over blijft. Zo ga je door met steeds kleinere staafjes in de loze ruimten te plaatsen. In de limiet is de "doos" 100% gevuld.

Het is waar as je een willekeurig groot getal neemt dat het aantal cilinders weergeeft. Dan is er altijd een loze ruimte over, maar dat is niet het zelfde als het proces van opvullen naar de limiet laten gaan.

Ook zou je gelijk hebben als je staafjes van gelijke diameter zou nemen en deze in the limiet naar een diameter van 0 laar gaan. . . dan is de ratio van de vulling tot de loze ruimte constant.