Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Metoda greedy |
Presupunem că avem două liste de coeficienți, unul cu numere negative și celălalt cu numere pozitive. Scopul este de a minimiza expresia suma( coeficienti_negativi * coeficienti_pozitivi ) .
# include < iostream >
void selectionSort ( int arr [], int n) {
for ( int i = 0 ; i < n - 1 ; i++) {
int min_index = i;
for ( int j = i + 1 ; j < n; j++) {
if ( arr [j] < arr [ min_index ]) {
min_index = j;
}
}
if ( min_index != i) {
int temp = arr [i];
arr [i] = arr [ min_index ];
arr [ min_index ] = temp ;
}
}
}
int main () {
int coeficienti_negativi [] = { -4 , -3 , -2 };
int coeficienti_pozitivi [] = { 1 , 2 , 3 };
int n = sizeof ( coeficienti_negativi ) / sizeof ( coeficienti_negativi [ 0 ]);
int m = sizeof ( coeficienti_pozitivi ) / sizeof ( coeficienti_pozitivi [ 0 ]);
selectionSort ( coeficienti_negativi , n);
selectionSort ( coeficienti_pozitivi , m);
int min_sum = 0 ;
for ( int i = 0 ; i < n; i++) {
min_sum += coeficienti_negativi [i] * coeficienti_pozitivi [i];
}
std :: cout << "Valoarea minima a expresiei este: " << min_sum << std :: endl ;
return 0 ;
}
void selectionSort ( int arr [], int n) {
for ( int i = 0 ; i < n - 1 ; i++) {
int min_index = i;
for ( int j = i + 1 ; j < n; j++) {
if ( arr [j] < arr [ min_index ]) {
min_index = j;
}
}
if ( min_index != i) {
int temp = arr [i];
arr [i] = arr [ min_index ];
arr [ min_index ] = temp ;
}
}
}
int main () {
int coeficienti_negativi [] = { -4 , -3 , -2 };
int coeficienti_pozitivi [] = { 1 , 2 , 3 };
int n = sizeof ( coeficienti_negativi ) / sizeof ( coeficienti_negativi [ 0 ]);
int m = sizeof ( coeficienti_pozitivi ) / sizeof ( coeficienti_pozitivi [ 0 ]);
selectionSort ( coeficienti_negativi , n);
selectionSort ( coeficienti_pozitivi , m);
int min_sum = 0 ;
for ( int i = 0 ; i < n; i++) {
min_sum += coeficienti_negativi [i] * coeficienti_pozitivi [i];
}
std :: cout << "Valoarea minima a expresiei este: " << min_sum << std :: endl ;
return 0 ;
}
Acest program conține două liste de coeficienți: coeficienti_negativi și coeficienti_pozitivi . Folosim funcția selectionSort () pentru a sorta cele două liste în ordine crescătoare. Apoi, calculăm valoarea minimă a expresiei prin înmulțirea fiecărui element din lista coeficienti_negativi cu elementul corespunzător din lista coeficienti_pozitivi și adunăm rezultatele.
Rețineți că acest exemplu este conceput doar pentru 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ă.