Avete un insieme di numeri di cui volete calcolare la somma totale. Potete sommare due numeri alla volta, inserendo il risultato nell’insieme di numeri, fino ad arrivare ad avere un numero solo, pari alla somma totale.
Il costo di una somma è pari al valore della somma stessa.Ad esempio, se volete sommare i numeri 2,3 e 7, possiamo ad esempio sommare 2 e 3, con costo 5, e poi sommare 5 e 7, con costo 12.
Il costo totale è quindi 5+12=17.
In alternativa, sommando prima 3 e 7 (costo 10) e poi 2 e 10 (costo 12), il costo totale per arrivare alla somma è 10+12=22.Se i numeri da sommare sono i seguenti: 2, 5, 6, 8, 10, 12, 20, 27 qual è il costo minimo C per sommarli tutti tra di loro?
Risposta: C=243
Le somme parziali devono essere le più basse possibile per ottenere il costo finale minimo.
A ogni passo bisogna scegliere la coppia di numeri più piccoli…
Osserva la sequenza di somme
- 2+5 = 7
- 6+7 = 13
- 8+10 = 18
- 12+13 = 25
- 18+20 = 38
- 25+27 = 52
- 38+52 = 90
Quindi: 7+13+18+25+38+52+90 = 243