[BASE Cinque - Appunti di Matematica ricreativa]

Il problema dello zaino

Knapsack problem

Questa pagina contiene un programma javascript. Se volete utilizzarla senza essere collegati ad internet potete salvarla sul vostro computer.

Immagina di essere un archeologo.
Hai trovato un tesoro in una caverna e hai soltanto uno zaino da riempire con oggetti di grande valore. Le pareti stanno crollando e non potrai più tornare in questo luogo perciò devi decidere adesso che cosa mettere in salvo, una volta per tutte.
Inoltre non puoi portare più di 27 kg di peso.

Ecco la lista degli oggetti. Quali sceglieresti, in modo da accumulare il più alto valore possibile?

Oggetto	Peso (kg)	Valore (migliaia di euro)	Rapporto valore/peso (€/g)
Statuetta crisoelefantina*	10	200	20
Maschera funeraria	12	225	18,75
Idolo d'oro	15	250	16,67
Spada	9	150	16,67
Scrigno	7	125	17,86
Sacchetto di perle	6	125	20,83
Sacchetto di monete	6	120	20
Scettro	6	120	20
Corona	4	75	18,75

*crisoelefantina: fatta d'oro e d'avorio

Prima di leggere le soluzioni che seguono, trova quella che secondo te è la soluzione migliore.
Ricorda che dovrai sempre tenere conto di due relazioni, la prima delle quali è una disequazione:
1) peso < 27 kg
2) valore = il maggiore fra tutti quelli possibili

Soluzione 1. Scegli gli oggetti più pesanti, così farai più in fretta a riempire lo zaino:
Idolo d'oro + Maschera funeraria, peso: 27 kg, valore: 475.000 euro
Soluzione 2. Scegli gli oggetti più leggeri, così ne salverai un numero maggiore:
Corona + Sacchetto di perle + Sacchetto di monete + Scettro; peso: 22 kg, valore: 440.000 euro
Soluzione 3. Scegli gli oggetti più preziosi, cioè quelli che hanno un maggiore rapporto valore/peso:
Sacchetto di perle + Statuetta crisoelefantina + Sacchetto di monete + Corona, peso: 26 kg, valore: 520.000 euro
Soluzione 4. Scegli gli oggetti che ti permettono di raggiungere il peso di 27 kg e il massimo valore in euro:
Statuetta crisoelefantina + Scrigno + Sacchetto di perle + Corona, peso: 27 kg, valore: 525.000 euro

Tutte le soluzioni presentano qualche vantaggio, ma la soluzione matematicamente ottima è la 4 perché ti permette di raggiungere il massimo, sia nel valore sia nel peso trasportato.

Qui sotto c'è un piccolo programma javascript con il quale potrai fare alcuni esperimenti.

E' già impostato con i dati del problema, ma se vuoi puoi modificarli e vedere che cosa succede.

Dati in ingresso

Inserisci qui il numero di oggetti (n) (max 15):

E qui il peso massimo consentito:

Scrivi ora i pesi degli oggetti:

Infine scrivi i rispettivi valori:

Attenzione: i pesi e i valori devono essere numeri interi o decimali separati da virgole e devono essere tanti quanti dichiarati nella casella "numero oggetti". Il programma non fa alcun controllo dei dati inseriti.

Clicca su un tasto e avrai la soluzione in un riquadro più sotto.

Spiegazione:

la funzione "brute force", forza bruta, esamina tutti i modi possibili di riempire lo zaino, che sono 2^n e stampa una soluzione ottimale (potrebbe essercene più di una). Per n>15 diventa molto lenta!
la funzione in "dynamic programming", programmazione dinamica, è tremendamente veloce ma funziona bene solo con numeri interi e comunque restituisce soltanto il massimo valore ottenibile.

Soluzione

Se vuoi creare un esercizio digita i parametri e clicca sul pulsante qui sotto.

Numero oggetti: - Peso massimo:

Spiegazione: il computer assegna pesi e valori casuali (compresi fra 1 e 11) al numero di oggetti richiesto e tenta di risolvere il problema.
Se superi i 15 oggetti, il programma utilizza l'algoritmo dynamic.
Ma ti prego, non andare oltre il 100.

Data creazione: agosto 2006

Ultimo aggiornamento: agosto 2006

xhtml 1.1

Sito Web realizzato da Gianfranco Bo