Knapsack – E1

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

 Minerale | Valore | Peso
----------+--------+------
 m1       | 15     | 35
 m2       | 19     | 46
 m3       | 14     | 25
 m4       | 10     | 12

Calcoli

 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

  1. L = [m2,m4]
  2. V = 29