indiana jones

[delfo52]

faccio riferimento al quesito dell'archeologo e della caverna che crolla, che è stato inserito su B5 da poche ore.
Mi pare che sia possibile una soluzione ancora più soddisfacente, anche se forse un poco "laterale".
Se consideriamo che i sacchetti di perle e di monete, dal peso di 6 chili ognuno, sono certamente composti di un grande numero di elementi, è possibile portarsi via 27 chili di materiale, tutto di valore"al chilo" superiore a 20
Adesso non ho sott'occhio la lista, ma ricordo che si tratta di un oggetto da 10 e tre oggetti da 6.
Uno ha valore unitario di 20,80 (cito a memoria), mentre gli altri valgono 20 precisi al chilo.
Tra questi ci sono le perle: basta dividere le perle (o le monete) in proporzione 5:1 e porteremo a casa 545mila euro di bottino.

Ma un vero archeologo non baderebbe a misere questioni valutarie, e farebbe una scelta che permetta di portare in salvo il numero maggiore e più vario di oggetti....

[Admin]

intervengo per segnalare che il problema dello zaino è un classico che viene proposto e riproposto nei corsi di Matematica Discreta e Ricerca Operativa.

Per risolvere problemi di questo tipo ho sempre utilizzato l'albero binario;
tuttavia, in questo caso si avrebbe un albero binario con 256 ramificazioni;
un pò difficile da costruire con carta e penna!

il problema dello zaino con il limite di peso, è uno splendido esempio di problema NP-completo.

Informazioni più dettagliate si possono trovare su Wikipedia:

http://it.wikipedia.org/wiki/Problema_dello_zaino
http://it.wikipedia.org/wiki/Classi_di_ ... %A0_P_e_NP
http://it.wikipedia.org/wiki/NP-completo



Ciao
Admin

[0-§]

Tornando al nostro problema,ho sviluppato(pistolando,incredibile ma vero, con Microsoft Word,ovvero un programma che nulla sembrerebbe avere a che fare con la matematica...non ho ancora imparato a trasformare il caffé in teoremi,ma ci sto provando seriamente ):il "problema dei molti zaini".
Qui non abbiamo la scelta tra cosa portare e cosa no:dobbiamo partire per un lungo viaggio e abbiamo una serie di n oggetti del peso di $a_1,a_2,a_3,...,a_n$ chili da portare forzosamente con noi(bussola,borraccia,vettovaglie etc.).Con noi abbiamo anche una serie di zaini,tutti uguali,capaci di portare ciascuno M chili.La somma dei pesi dei vari oggetti supera abbondantemente M,quindi ci toccherà portare sicuramente più di uno zaino;gli zaini disponibili possono portare complessivamente molto più della somma dei pesi degli n oggetti,quindi ci saranno sicuramente degli zaini di cui potremo fare a meno.Per ovvie ragioni di ingombro e di praticità,vorremmo usare meno zaini possibile.Esiste un algoritmo per decidere come ripartire i pesi negli zaini in modo da soddisfare tutte le condizioni sopra esposte?
Questo problema ovviamente ha senso solo se consideriamo un numero elevato di oggetti,con un peso molto variabile:in tal caso incastrare al meglio gli oggetti nei vari zaini diventa una lavoraccio e disporre di un computer per poter programmare il tutto sarebbe un bel guadagno.
Se il problema di base vi sembra troppo semplice e avete una gran voglia di masticarvi inutilmente il cervello,ho in mente alcune delle mie famigerate estensioni,ma ora é veramente troppo tardi per pensarci su.(beh,non é detto:almeno la possibilità che gli zaini abbiano una capienza non uguale ma variabile all'interno di un range noto la propongo fin d'ora...)
Bene,vado a letto e saluto i basecinquini dopo questa intensa giornata...A prestissimo,spero.
Con affetto,
Zerinf