Il problema dello zaino

Knapsack problem

Immagina di essere un archeologo che ha trovato un tesoro in una caverna e ha soltanto uno zaino da riempire con oggetti di grande valore. Devi fare presto perché tutto sta crollando e hai solo pochi momenti a disposizione per mettere in salvo gli oggetti con il massimo valore possibile e con un peso max. di 27 kg

Oggetto Peso

(kg)

 Valore

(€ migliaia)

 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

Prima di leggere le soluzioni che seguono prova a dare una risposta calcolando quale valore massimo e possibile raggiungere senza superare il peso di 27 kg

guarda la soluzione