In un deposito di minerali esistono esemplari di vario peso e valore individuati da sigle di riconoscimento.
Ciascun minerale è descritto da una sigla che contiene le seguenti informazioni:
tab(<sigla del minerale>, <valore in euro>, <peso in Kg>).
Il deposito contiene i seguenti minerali:
tab(m1,15,35), tab(m2,19,46), tab(m3,14,25), tab(m4,10,12)
Disponendo di un piccolo motocarro con portata massima di 59 Kg trovare la lista L delle sigle di due minerali diversi che siano trasportabili contemporaneamente con questo mezzo e che abbiano il massimo valore complessivo; calcolare inoltre questo valore V.
N.B. Nella lista, elencare le sigle in ordine (lessicale) crescente; per le sigle usate si ha il seguente ordine: m1 < m2 < m3 < … .
DISCUSSIONE
Dati
|
1 2 3 4 5 6 |
Minerale | Valore | Peso ----------+--------+------ m1 | 15 | 35 m2 | 19 | 46 m3 | 14 | 25 m4 | 10 | 12 |
Calcoli
|
1 2 3 4 5 6 7 8 |
Combinazioni | Peso | <= 59 | Valore --------------+----------+-------+---------- [m1,m2] | 35+46=81 | | [m1,m3] | 35+25=60 | | [m1,m4] | 35+12=47 | Sì | 15+10=25 [m2,m3] | 46+25=71 | | [m2,m4] | 46+12=58 | Sì | 19+10=29 [m3,m4] | 25+12=37 | Sì | 14+10=24 |
Risposte
- L = [m2,m4]
- V = 29