Vai al contenuto principale
← OlimpiApp Difficile

Informatica · Greedy

Risparmio dell'ordine ottimo sulla coda a sportello

A uno sportello arrivano 7 pratiche, da elaborare una alla volta a partire dal tempo 0. La pratica i richiede $t_{i}$ minuti e ha importanza $w_{i}$; il disagio totale è la somma dei $w_{i} \cdot C_{i}$, dove $C_{i}$ è il minuto in cui la pratica i viene completata.
Nell'ordine di arrivo le pratiche sono: ($t=4$, $w=1$), ($t=2$, $w=7$), ($t=6$, $w=3$), ($t=1$, $w=4$), ($t=3$, $w=5$), ($t=5$, $w=2$), ($t=2$, $w=2$).
Di quanto diminuisce il disagio totale passando dall'ordine di arrivo a un ordine ottimo?

La tua risposta

Vanno bene sia 3,14 sia 3.14.