Quanti parallelepipedi/cubi ci stanno in un parallelepipedo contenitore?

[matteoxzibit]

Buongiorno a tutti, avrei bisogno del vostro aiuto per la creazione di un "algoritmo" che mi permetta di calcolare quanti parallelepipedi o cubi ci possono stare in un'altro parallelepipedo che faccia da contenitore. Il tutto in modo che possano occupare il minor spazio possibile, quindi con la capacità di essere ruotati/capovolti.

Per farvi un esempio pratico: il parallelepipedo contenitore potrebbe essere un furgone e i cubi/parallepipedi da inserire sono i pacchi, in che modo posso calcolare come caricarli al meglio occupando meno spazio?

Grazie a chi mi risponderà, io sono in altro mare!

[nRT]

Ciao,
è sufficiente che calcoli le sei combinazioni e scegli quella in cui ci possono stare più scatole.

Dette:
a = larghezza scatola;
b = altezza scatola;
c = profondità scatola;
x = larghezza contenitore;
y = altezza contenitore;
z = profondità contenitore;

Le possibilità si calcolano nel seguente modo usando variabili intere senza segno (cioè in modo che

[math]\frac{45}{5} = \frac{49}{5} = 9[/math]

)

numScatole1 = ( x / a ) * ( y / b ) * ( z / c ); // L = l, H = h, P = p
numScatole2 = ( x / a ) * ( y / c ) * ( z / b ); // L = l, H = p, P = h
numScatole3 = ( x / b ) * ( y / a ) * ( z / c ); // ecc...
numScatole4 = ( x / b ) * ( y / c ) * ( z / a );
numScatole5 = ( x / c ) * ( y / a ) * ( z / b );
numScatole6 = ( x / c ) * ( y / b ) * ( z / a );
... ...

Se ci sono oggetti che non si possono mettere in determinate posizioni, o capovolgere, andrebbero escluse tali possibilità prima del calcolo.

Una volta completato questo passaggio, si ricava lo spazio rimasto, che si può dividere virtualmente in altri parallelepipedi. Ad esempio, nel caso di numScatole1, calcoli il parallelepipedo di dimensioni ( x - x / a ; y; z ), e si verifica la possibilità di riempirlo ad un'altezza ( y - y / b ), in modo da avere un piano comodo per lavorare e calcolare poi facilmente lo spazio rimasto, e si ripete il procedimento fino a quando lo spazio rimasto non permette di mettere più neanche una scatola.

Terminate le soluzioni, il programma sceglierà quella con il maggior numero di scatole.

Questa penso sia una soluzione accettabile anche considerando la facilità di riempimento.

Esistono soluzioni più efficienti di questa, anche se potrebbero richiedere più tempo lavorativo per riempire le scatole secondo uno schema più complesso. Ad esempio:
le scatole hanno dimensione:
a = 7;
b = 10;
c = 30;
i contenitori:
x = 140;
y = 24;
z = 30;

Con il sistema di cui sopra si troverebbe la soluzione che permette di mettere 42 scatole, mentre studiando bene il sistema, ce ne starebbero 48.
Infatti, dovremmo calcolare le combinazioni per cui

ia + bj + kc

dia il risultato più vicino (arrotondato sempre per difetto) a 24 nel nostro caso. Si verifica poi lo spazio rimanente con quella combinazione, e poi facciamo scegliere al programma il risultato più conveniente. Troviamo quindi che:

2a + b = y
c = z
20a = x
14b = x

Per cui ci stanno due file di scatole da 10 x 7 x 30 + una fila di scatole da 7 x 10 x 30.
In totale, due file di 140 / 10 = 14 scatole più una fila di 140 / 7 = 20 scatole, 48 scatole.

Questo procedimento richiede ovviamente più lavoro di progettazione, ma dà risultati migliori.

Spero ti sia stato d'aiuto per darti un'idea su cui lavorare.
Ciao :)