Vedi la discussione (coppie di minerali)
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 < … .
Soluzione 1
VALORI = [15, 19, 14, 10]
PESI = [35, 46, 25, 12]
PESO_MAX = 59
sol_min_1 = -1
sol_min_2 = -1
sol_valore = 0
sol_peso = 0
n = len(PESI)
for i in range(n):
for j in range(i+1, n):
# ---------------------------- Nuova coppia
valore = VALORI[i] + VALORI[j]
peso = PESI[i] + PESI[j]
print(i+1, j+1, valore, peso, sep="\t")
# ---------------------------- Nuova soluzione?
if(peso <= PESO_MAX) and (valore > sol_valore):
sol_min_1 = i
sol_min_2 = j
sol_valore = valore
sol_peso = peso
print()
print(sol_min_1+1, sol_min_2+1, sol_valore, sol_peso, sep="\t")
Stampa la tabella con tutti i casi e dopo la riga della soluzione.
Gli indici delle liste partono da zero, visualizza gli indici aumentati di 1.
1 2 34 81
1 3 29 60
1 4 25 47
2 3 33 71
2 4 29 58
3 4 24 37
2 4 29 58
Soluzione 2
Una lista contiene i nomi dei minerali che verranno visualizzati nella soluzione
NOMI = ["m1", "m2", "m3", "m4"]
VALORI = [15, 19, 14, 10]
PESI = [35, 46, 25, 12]
PESO_MAX = 59
sol_nome = ""
sol_valore = 0
sol_peso = 0
n = len(PESI)
for i in range(n):
for j in range(i+1, n):
# ---------------------------- Nuova coppia
nome = NOMI[i] + "+" + NOMI[j]
valore = VALORI[i] + VALORI[j]
peso = PESI[i] + PESI[j]
print(nome, valore, peso, sep="\t")
# ---------------------------- Nuova soluzione?
if(peso <= PESO_MAX) and (valore > sol_valore):
sol_nome = nome
sol_valore = valore
sol_peso = peso
print()
print(sol_nome, sol_valore, sol_peso, sep="\t")
m1+m2 34 81
m1+m3 29 60
m1+m4 25 47
m2+m3 33 71
m2+m4 29 58
m3+m4 24 37
m2+m4 29 58
Soluzione 3
La classe minerale permette di eliminare le liste parallele per i nomi, valori, pesi.
class minerale:
def __init__(self, nome, valore, peso):
self.nome = nome
self.valore = valore
self.peso = peso
def __str__(self):
return f"{self.nome}, valore={self.valore}, peso={self.peso}"
#--------------------------------------------------------------------
MINERALI = [ minerale("m1", 15, 35),
minerale("m2", 19, 46),
minerale("m3", 14, 25),
minerale("m4", 10, 12)
]
PESO_MAX = 59
#--------------------------------------------------------------------
soluzione = minerale("", 0, 0)
n = len(MINERALI)
for i in range(n):
for j in range(i+1, n):
# ------------------------------------ Nuova coppia
m_1 = MINERALI[i]
m_2 = MINERALI[j]
# ------------------------------------ Nuovo "minerale"
m = minerale(m_1.nome + "+" + m_2.nome,
m_1.valore + m_2.valore,
m_1.peso + m_2.peso)
print(m)
# ------------------------------------ Nuova soluzione?
if(m.peso <= PESO_MAX) and (m.valore > soluzione.valore):
soluzione = m
#--------------------------------------------------------------------
print()
print(soluzione)
m1+m2, valore=34, peso=81
m1+m3, valore=29, peso=60
m1+m4, valore=25, peso=47
m2+m3, valore=33, peso=71
m2+m4, valore=29, peso=58
m3+m4, valore=24, peso=37
m2+m4, valore=29, peso=58
Miglioramenti
- Se il peso totale di due minerali non rientra nel limite massimo si può evitare di procedere con il calcolo del valore totale.
- Nel caso in cui i minerali fossero centinaia/migliaia il numero di coppie crescerebbe in modo quadratico (?).
- Se si ordinano i minerali per peso crescente allora la prima coppia che supera il peso massimo determina l’esclusione di tutte le coppie successive.