Problema Algoritmo dello zaino.
Salve a tutti!
Scrivo questo messaggio per chiedervi un aiuto. Premetto che non sono uno studente ma un appassionato e non dispongo ancora delle nozioni per risolvere il che problema che sto per esporvi.
Dalle mie ricerche ho visto che la soluzione è l'algoritmo dello zaino però io ho dei dati diversi di partenza ed è per questo che son andato in panico.
In pratica il problema è questo:
Ho un certo numero di oggetti rettangolari di cui conosco le misure. Devo ricavare tutti questi oggetti avendo più zaini a mia disposizione (per esempio 5) .
A differenza del classico problema dello zaino, non devono essere considerati i dati del peso ed il valore degli oggetti ma solo le loro dimensioni. In più l'algoritmo deve ricavare sempre ed in ogni caso tutti gli oggetti indicati in partenza scegliendo la combinazione di zaini migliore.
Qualcuno mi sa indicare la formula dell'algoritmo e la sua risoluzione?
Chiedo scusa se nella spiegazione ho usato termini non consoni.
Grazie
Scrivo questo messaggio per chiedervi un aiuto. Premetto che non sono uno studente ma un appassionato e non dispongo ancora delle nozioni per risolvere il che problema che sto per esporvi.
Dalle mie ricerche ho visto che la soluzione è l'algoritmo dello zaino però io ho dei dati diversi di partenza ed è per questo che son andato in panico.
In pratica il problema è questo:
Ho un certo numero di oggetti rettangolari di cui conosco le misure. Devo ricavare tutti questi oggetti avendo più zaini a mia disposizione (per esempio 5) .
A differenza del classico problema dello zaino, non devono essere considerati i dati del peso ed il valore degli oggetti ma solo le loro dimensioni. In più l'algoritmo deve ricavare sempre ed in ogni caso tutti gli oggetti indicati in partenza scegliendo la combinazione di zaini migliore.
Qualcuno mi sa indicare la formula dell'algoritmo e la sua risoluzione?
Chiedo scusa se nella spiegazione ho usato termini non consoni.
Grazie
Risposte
Allora, capiamoci perché la cosa è un po' confusa. Tu hai $n$ oggetti di cui conosci tutte le dimensioni, e suppongo che gli oggetti siano parallelepipedi (non rettangoli!). Inoltre hai $N$ contenitori e ti chiedi quale sia "l'impacchettamento" migliore per distribuire questi oggetti nei vari contenitori, tenuto conto delle dimensioni degli oggetti stessi e, suppongo, anche delle dimensioni dei contenitori, è così?
X ciampax
Ciao e grazie per avermi risposto. Infatti hai ragione sono parallelepipedi mentre per quanto riguarda la descrizione del problema la tua è molto più chiara e comunque sia è quello il problema.
Grazie ancora per la risposta, nel caso devo darti ulteriori informazioni io sono qua.
Ciao
Ciao e grazie per avermi risposto. Infatti hai ragione sono parallelepipedi mentre per quanto riguarda la descrizione del problema la tua è molto più chiara e comunque sia è quello il problema.
Grazie ancora per la risposta, nel caso devo darti ulteriori informazioni io sono qua.
Ciao
x gio73
ciao e grazie anche a te per avermi linkato il post.
Ciao
ciao e grazie anche a te per avermi linkato il post.
Ciao
In tutto questo manca un pezzo, mi sembra:
Come dici se una combinazione è migliore di un'altra?
"Luce84":
[...] scegliendo la combinazione di zaini migliore.
Come dici se una combinazione è migliore di un'altra?
Ciao Raptorista e grazie anche a te per aver partecipato alla discussione.
Mi rendo conto e vi chiedo scusa per il modo in cui ho espresso il mio problema, magari utilizzando un linguaggio troppo semplice ma come detto all'inizio non sono un matematico ma sto cercando di risolvere un problema e allo stesso tempo voglio imparare qualcosa.
Adottando parole proprio semplici, l'algoritmo deve saper fare questo:
Conoscendo le misure di uno o più parallelepipedi iniziali e avendo a disposizione uno o più contenitori (o zaini) anche questi con forma parallelepipeda; l'algoritmo mi deve saper indicare la migliore disposizione dei parallelepipedi iniziali su uno o più contenitori a mia disposizione in modo da poterli ricavare tutti (parallelepipedi iniziali)utilizzando la minor quantità di contenitori a mia disposizione.
Ciao!
Mi rendo conto e vi chiedo scusa per il modo in cui ho espresso il mio problema, magari utilizzando un linguaggio troppo semplice ma come detto all'inizio non sono un matematico ma sto cercando di risolvere un problema e allo stesso tempo voglio imparare qualcosa.
Adottando parole proprio semplici, l'algoritmo deve saper fare questo:
Conoscendo le misure di uno o più parallelepipedi iniziali e avendo a disposizione uno o più contenitori (o zaini) anche questi con forma parallelepipeda; l'algoritmo mi deve saper indicare la migliore disposizione dei parallelepipedi iniziali su uno o più contenitori a mia disposizione in modo da poterli ricavare tutti (parallelepipedi iniziali)utilizzando la minor quantità di contenitori a mia disposizione.
Ciao!
Ok, adesso la formulazione è più chiara. Per inciso, non era necessario riscrivere tutta la pappardella, ma solamente "utilizzando la minor quantità di contenitori a mia disposizione"; era quello che mancava.
Se non ti interessa LA soluzione ottima, ma solo una soluzione buona, potresti pensare di usare un algoritmo greedy, soprattutto se i dati sono tanti.
Se non ti interessa LA soluzione ottima, ma solo una soluzione buona, potresti pensare di usare un algoritmo greedy, soprattutto se i dati sono tanti.
In realtà quella condizione non è ancora sufficiente per avere un unico massimo. Per prima cosa c'è l'inevitabile possibilità di ridistribuire in modo diverso gli oggetti negli stessi scatoloni. Questa possibilità è difficile se non impossibile da evitare. Inoltre se io ho due scatoloni, uno dei quali che può essere completamente contenuto nell'altro allora posso spostare l'intero contenuto del primo nel secondo mantenendo lo stesso numero di scatoloni riempiti.
Si può richiedere che, per esempio, il volume totale degli scatoloni usati sia minimo. Ma bisogna stare attenti perché aggiungere la condizione richiede di gestire il fatto che le due condizione potrebbero avere un diverso minimo. Inoltre trovare questo tipo di cose in presenza di più condizioni è generalmente evitato.
Si può richiedere che, per esempio, il volume totale degli scatoloni usati sia minimo. Ma bisogna stare attenti perché aggiungere la condizione richiede di gestire il fatto che le due condizione potrebbero avere un diverso minimo. Inoltre trovare questo tipo di cose in presenza di più condizioni è generalmente evitato.
@vict: vero, ma... Ha importanza che il massimo sia unico?
Non sono sicuro. Dipende un po' da che metodo si utilizza per risolvere il problema.
Ciao ragazzi!
Alla luce di tutte queste informazioni mi pare capire che non ho tante possibilità, quindi come posso fare?
Il mio obiettivo è trovare una soluzione ottima, poi se mi devo accontentare (optando per l'algoritmo di greedy) lo faccio lo stesso ma vorrei lottare un pò prima di gettare la spugna. Altre alternative o studi?
Di nuovo grazie a tutti e spero che qualcosa ci illumini.
Alla luce di tutte queste informazioni mi pare capire che non ho tante possibilità, quindi come posso fare?
Il mio obiettivo è trovare una soluzione ottima, poi se mi devo accontentare (optando per l'algoritmo di greedy) lo faccio lo stesso ma vorrei lottare un pò prima di gettare la spugna. Altre alternative o studi?
Di nuovo grazie a tutti e spero che qualcosa ci illumini.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo