Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Metoda greedy |
Când toți coeficienții sunt negativi și toate elementele din mulțimea A sunt pozitive, problema de optimizare constă în minimizarea valorii unei funcții liniare, în loc de maximizare, cum ar fi cazul în care coeficienții sunt pozitivi.
Pentru a minimiza funcția liniară în aceste condiții, trebuie să aplicăm următorul criteriu de prioritate:
Motivul pentru care aplicăm acest criteriu de prioritate este că, atunci când avem coeficienți negativi, dorim să "echilibram" valoarea negativă a coeficienților cu cea mai mică valoare pozitivă a elementelor din mulțimea A, astfel încât să obținem o valoare cât mai mică pentru funcția liniară. Prin împerecherea coeficienților negativi cu elementele cele mai mici din mulțimea A, vom minimiza valoarea funcției liniare.
Rețineți că acest criteriu de prioritate este valid doar în cazul în care coeficienții sunt negativi și toate elementele din mulțimea A sunt pozitive. Dacă aveți o combinație de coeficienți pozitivi și negativi sau dacă mulțimea A conține și valori negative, problema de optimizare devine mai complexă și nu poate fi rezolvată doar prin aplicarea metodei greedy . În aceste cazuri, ar fi necesară o abordare mai generală, cum ar fi programarea liniară sau algoritmi de căutare exhaustivă, pentru a găsi soluția optimă.
P roblema schimbului de monezi.
# include < iostream >
void greedyCoinChange ( int monede[], int numarMonede , int suma) {
int rezultat[ numarMonede ];
int i, contorMonede = 0 ;
for (i = numarMonede - 1 ; i >= 0 ; i--) {
while (suma >= monede[i]) {
suma -= monede[i];
rezultat[ contorMonede ++] = monede[i];
}
}
std :: cout << "Monezile folosite sunt: " ;
for (i = 0 ; i < contorMonede ; i++) {
std :: cout << rezultat[i] << " " ;
}
}
int main () {
int monede[] = { 1 , 5 , 10 , 20 , 50 , 100 };
int numarMonede = sizeof (monede) / sizeof (monede[ 0 ]);
int suma = 263 ;
greedyCoinChange (monede, numarMonede , suma);
return 0 ;
}
void greedyCoinChange ( int monede[], int numarMonede , int suma) {
int rezultat[ numarMonede ];
int i, contorMonede = 0 ;
for (i = numarMonede - 1 ; i >= 0 ; i--) {
while (suma >= monede[i]) {
suma -= monede[i];
rezultat[ contorMonede ++] = monede[i];
}
}
std :: cout << "Monezile folosite sunt: " ;
for (i = 0 ; i < contorMonede ; i++) {
std :: cout << rezultat[i] << " " ;
}
}
int main () {
int monede[] = { 1 , 5 , 10 , 20 , 50 , 100 };
int numarMonede = sizeof (monede) / sizeof (monede[ 0 ]);
int suma = 263 ;
greedyCoinChange (monede, numarMonede , suma);
return 0 ;
}
Acest exemplu abordează problema schimbului de monezi folosind metoda greedy . Avem un set de monede disponibile și o sumă pe care dorim să o obținem folosind cât mai puține monede posibil. Funcția greedyCoinChange primește ca parametri un array de monede, numărul de monede disponibile și suma pe care dorim să o obținem.
Metoda greedy este aplicată prin parcurgerea monedelor de la cea mai mare valoare la cea mai mică, adăugând cât mai multe monede posibil de valoarea curentă fără a depăși suma dorită. Aceasta se face folosind o buclă while care scade valoarea monedei curente din suma și adaugă moneda în array-ul rezultat .
După ce bucla se încheie, programul afișează monedele folosite pentru a obține suma dorită.
Rețineți că acest exemplu funcționează corect doar pentru sisteme de monede în care metoda greedy oferă soluția optimă. Pentru sisteme de monede în care metoda greedy nu garantează soluția optimă, ar fi necesar să apelați la alte tehnici de rezolvare, cum ar fi programarea dinamică.