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.

Puoi sperimentare le soluzioni con il programma Java già impostato

 

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.