[PHP] Berekening aantal producten in een doos

[robg1984]

(Niet direct een programmeervraag. Wanneer het niet in dit forum thuis hoort, mijn excuses.)

Op een website van een klant van me kun je een soort van kerstpakketten zelf samenstellen met producten.Door middel van de afmetingen van de doos en de afmetingen van de producten wil ik kijken wanneer de doos vol is.

In de database staat per doos en per product de afmetingen en de totale inhoud (cm3).

(Voorbeeld)
Stel een doos is 50x50x50cm.
Dit is 125000cm3.

Een product is 30x30x30cm.
Dit is 27000cm3

Volgens mijn berekening zou het product 4,6x erin passen maar dat past in werkelijkheid natuurlijk nooit!
Je kunt het product namelijk niet naast of op elkaar in de doos krijgen omdat het dan hoger is dan de doos zelf.

Welke berekening heb ik wel nodig om te kijken of de doos vol zit?

Ik heb ook nog het volgende bedacht:

3 categorieen producten (klein middel groot)
cat klein = 1 credit per product
cat middel = 5 credits per product
cat groot = 10 credits per product

bij een doos van 10 credits (vooraf definieren hoeveel credits erin passen). zou dus 10 kleine producten passen, 2 middel of 1 grote. Of natuurlijk 1 middel en 5 kleine...

bij een doos van 20 credits. zou dus 20 kleine producten passen, 4 middel of 2 grote. Of natuurlijk 2 middel en 10 kleine...

zou dit iets zijn?

[KopjeThee]

Een beetje googelen op Packing problem kan misschien iets helpen.

[RobIII]

Of Wikipedia: Knapsack problem

[Soultaker]

Specifieker Bin Packing. (Knapsack is eigenlijk wat anders en heeft ook andersoortige oplossingen) Simpele instanties (met kleine, geheeltallige afmetingen en kleine aantallen producten) zijn wel optimaal op te lossen, maar de kans is groot dat je er dan zelf met de hand ook nog niet uitkomt.

Praktisch lijkt je suggestie van een aantal categoriën me een stuk zinniger, maar het hangt een beetje van de details af; hoe erg is het als een doos niet optimaal benut wordt?

Overigens kun je met greedy algoritmen nog wel een heel eind komen, maar zelfs die zijn enigzins lastig te implementeren. Ik zou daar alleen aan beginnen als je het gewoon leuk vind.

[ Voor 14% gewijzigd door Soultaker op 07-04-2008 21:21 ]

[BestTested!]

RobIII schreef op maandag 07 april 2008 @ 19:46:
Of Wikipedia: Knapsack problem

Knapsack problem, packing problem. Dit probleem is toch letterlijk het Bin Packing problem

edit:
Soultaker is me net voor: laat ik dan nog dit zeggen, ga niet voor een optimaal algorithme maar voor een benadering. In de meeste gevallen is dit 'goed genoeg' en is het de moeite niet waard om het probleem precies op te lossen

[ Voor 25% gewijzigd door BestTested! op 07-04-2008 21:22 ]

[robg1984]

Bedankt voor de tips.
Na het zoeken naar Bin Packing Problem erachter gekomen dat er geen precieze oplossing is.
Ik denk dat ik toch maar voor het idee met de categorieen ga (en rekening houden met een bepaalde marge). Ik denk dat het dan in veel gevallen wel ongeveer zou moeten kloppen? Jammer dat er dan in sommige gevallen nog zat ruimte over is, maar goed, je moet ook beschermmateriaal in de doos hebben!

[RobIII]

Soultaker schreef op maandag 07 april 2008 @ 21:18:
(Knapsack is eigenlijk wat anders en heeft ook andersoortige oplossingen)

Dat stond er ook al Het was meer bedoeld als aanvulling en meer linkjes die op die pagina staan

[ Voor 23% gewijzigd door RobIII op 07-04-2008 23:16 ]

[Verwijderd]

In plaats van afmetingen etc te gebruiken zou je toch ook zelf kunnen bekijken welke mogelijkheden in een doos passen (uitproberen) en dit vervolgens gebruiken als data?

[BestTested!]

robg1984 schreef op maandag 07 april 2008 @ 22:48:
Bedankt voor de tips.
Na het zoeken naar Bin Packing Problem erachter gekomen dat er geen precieze oplossing is.
Ik denk dat ik toch maar voor het idee met de categorieen ga (en rekening houden met een bepaalde marge). Ik denk dat het dan in veel gevallen wel ongeveer zou moeten kloppen? Jammer dat er dan in sommige gevallen nog zat ruimte over is, maar goed, je moet ook beschermmateriaal in de doos hebben!

[theorie-modus] Dat het een NP-hard probleem is betekent nog niet dat er geen precieze oplossing is [/theorie-modus].

Er zijn genoeg heuristieken te vinden die een goede benadering geven, maar je kan natuurlijk ook zelf iets verzinnen.