#Problemi greedyCome suggerisce il nome, nei problemi che vedremo tra poco la strategia vincente è comportarsi da avari, ovvero in ogni momento scegliere la soluzione localmente ottima. Analizziamo ad esempio la seguente situazione:
Gelati costosi
Ci servono 𝐶 soldi per comprare il gelato e 𝑁 nostri amici sono disposti a prestarcene un po’. L’𝑖-esimo amico ci può prestare al massimo 𝑃𝑖 soldi. Qual è il numero minimo di amici a cui dobbiamo chiedere in prestito dei soldi per poter prendere il gelato?
Prova il problema online: https://training.olinfo.it/task/pre-egoi-gelato
Soluzione
È un problema abbastanza semplice di cui sappiamo delineare intuitivamente una strategia risolutiva: chiedo ogni volta all’amico che mi dà più soldi finché non arrivo ad avere 𝐶 soldi.
Questa strategia si rivela essere quella ottimale! Di seguito l’implementazione:
int presta(int N, int C, vector<int> P) {
sort(begin(P), end(P));
int risposta = 0;
while (C > 0) {
risposta++;
C -= P.back();
P.pop_back();
}
return risposta;
}
La lezione che ne traiamo è che, in certi problemi, a una scelta localmente ottima formulata nel modo corretto (in questo caso chiedere ogni volta all’amico che ci dà più soldi) corrisponde una soluzione globalmente ottima (che per questo problema significa minimizzare il numero di amici a cui chiedere).
Un possibile criterio che ci suggerisce che il problema si possa risolvere in modo greedy è che le scelte che facciamo siano indipendenti tra loro. In questo caso chiedere a un amico non pone vincoli sugli amici ai quali potremo chiedere successivamente.
Ad ogni modo, il miglior metro per capire se a un problema si possa applicare un approccio greedy è l’esperienza. Vediamo quindi altri problemi:
Viaggio in taxi OIS2014-15
Dobbiamo passare per 𝑁 città in fila (numerate da 0 a 𝑁−1), equidistanti tra loro, e arrivare alla fine nella città numero 𝑁. Nella città 𝑖 è presente un taxi che ci può portare alla città successiva 𝑖+1 a un costo di 𝐶𝑖 soldi. Arrivati alla città successiva, se non siamo arrivati alla città 𝑁, possiamo scegliere se proseguire prendendo il taxi presente in quella città per 𝐶𝑖+1 soldi o rimanere sullo stesso taxi, che però aumenterà di 1 soldo il suo prezzo per ogni città successiva alla propria città di partenza.
Prova il problema online: https://training.olinfo.it/task/ois_taxi
Soluzione
Facendo un esempio per capire meglio il testo, se nella prima città il taxi costa 3 soldi, possiamo pagare 3 per prenderlo e andare alla seconda città. Se nella seconda città il taxi costa 5, possiamo scegliere se prendere quel taxi pagando 5 o rimanere sul nostro taxi pagando questa volta 4. Se rimaniamo sul nostro taxi, alla stazione successiva pagheremo 5, e così via.
Anche in questo problema la strategia intuitiva di prendere sempre il taxi che ci costa meno funziona perché in ogni caso entrambi aumenterebbero il loro prezzo di 1 soldo a ogni stazione successiva. Quindi se il taxi 𝐴 costa meno del taxi 𝐵 in una certa città, costerà di meno anche in tutte le successive.
int viaggia(int N, vector<int> C) {
int costo_totale = 0;
int costo_attuale = INT_MAX;
for (int i = 0; i < N; i++) {
if (costo_attuale > C[i])
costo_attuale = C[i];
costo_totale += costo_attuale;
costo_attuale += 1;
}
return costo_totale;
}
Mozzarelle di bufala OII2013
Ci sono 𝑁 mozzarelle (𝑁 è un numero pari). Alla 𝑖-esima mozzarella Monica dà il voto 𝑀𝑖 e Paola il voto 𝑃𝑖. Dobbiamo dividere le mozzarelle in due gruppi da 𝑁2 ciascuno in modo da massimizzare la somma dei voti nel rispettivo gruppo, cioè la somma dei voti che Monica dà alle sue 𝑁2 mozzarelle + i voti che Paola dà alle altre 𝑁2 mozzarelle.
Prova il problema online: https://training.olinfo.it/task/oii_bufale
Soluzione
In questo caso il primo approccio greedy che viene in mente potrebbe essere quello di ordinare le mozzarelle per uno dei due voti – diciamo quello di Monica – per poi assegnare le prime 𝑁2 a Monica e le restanti a Paola.
Questa strategia non funziona perché non stiamo tenendo conto di entrambi i voti: supponiamo di avere solo due mozzarelle; la prima vale 10 per Monica e 9 per Paola e la seconda vale 8 per Monica e 2 per Paola. Seguendo la precedente strategia finiremmo per assegnare la prima a Monica ottenendo somma 12 quando è ottimale il contrario, riuscendo ad ottenere somma 17.
Da questa osservazione ci potrebbe venire in mente di dividere le mozzarelle in base a quanto cambia assegnarla a Monica anziché a Paola. Una mozzarella che vale 10 per la prima e 9 per la seconda è meno rilevante di una che vale 8 per la prima e 2 per la seconda.
Per fare ciò ordiniamo le mozzarelle per la differenza tra il voto che dà Monica e quello che dà Paola.
Posto 𝐷𝑖=𝑀𝑖−𝑃𝑖, le mozzarelle con 𝐷𝑖 alto sono preferite da Monica rispetto a Paola; viceversa, se 𝐷𝑖 è piccolo, sarà più conveniente assegnarle a Paola. Questa soluzione si rivela essere ottimale.
long long solve(int N, int* M, int* P) {
vector<pair<int, int>> D(N);
for (int i = 0; i < N; i++) {
D[i] = {M[i] - P[i], i};
}
sort(begin(D), end(D));
long long somma = 0;
for (int i = 0; i < N; i++) {
int idx = D[i].second;
if (i < N / 2) {
somma += P[idx];
} else {
somma += M[idx];
}
}
return somma;
}
Note sull’implementazione:
•𝐷 contiene anche l’indice cui la differenza si riferisce in modo da poter risalire alla mozzarella una volta ordinate le differenze.•𝐷 è ordinato in ordine crescente, quindi le prime mozzarelle saranno quelle con 𝐷𝑖 più basso, da assegnare a Paola.•Curiosità: sarebbe possibile risolvere il problema in 𝒪︀(𝑁) utilizzando l’algoritmo std::nth_element della STL per trovare il valore della differenza secondo cui dividere le mozzarelle.I problemi greedy possono apparire semplici, tuttavia in certi casi trovare la strategia localmente ottima non è per nulla banale (vedi gli esercizi suggeriti).
#Problemi consigliati
Bus Excursion (https://training.olinfo.it/task/ois_excursion2)
Maximum Subarray Sum (https://cses.fi/problemset/task/1643)
Episodio I: un acquisto difficile (https://training.olinfo.it/task/oii_acquisti)
Vetrate colorate (https://training.olinfo.it/task/oii_artemoderna)
Library of Binaria (https://training.olinfo.it/task/ois_binaria)
Il pozzo (https://training.olinfo.it/task/pozzo)