Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Metoda greedy |
În cazul în care coeficienții sunt pozitivi și în mulțimea A nu există decât numere negative, criteriul de prioritate trebuie să fie astfel încât să optimizeze rezultatul, în funcție de scopul problemei.
De exemplu, să presupunem că obiectivul este de a obține cea mai mare valoare posibilă pentru o funcție liniară:
f(x) = a1 * x1 + a2 * x2 + ... + an * xn
Unde a1, a2, ..., an sunt coeficienții pozitivi și x1, x2, ..., xn sunt numerele negative din mulțimea A.
În acest caz, pentru a obține cea mai mare valoare posibilă pentru funcția liniară, trebuie să atribuim cel mai mare coeficient ( a_i ) celui mai mic număr negativ ( x_j ) din mulțimea A. Astfel, produsul a_i * x_j va fi cel mai mare posibil, având în vedere că ambele numere au semne diferite. Acest criteriu de prioritate va conduce la optimizarea rezultatului.
Acest criteriu de prioritate se bazează pe ideea că, pentru a maximiza valoarea unei funcții liniare cu coeficienți pozitivi și variabile negative, trebuie să "potrivim" coeficienții cu variabilele în ordine descrescătoare a coeficienților și în ordine crescătoare a variabilelor. Acest lucru ne asigură că produsele parțiale sunt cât mai mari posibil, ducând la o valoare optimă a funcției liniare.
# include < iostream >
using namespace std ;
void sort_descending ( double arr [], int n) {
for ( int i = 0 ; i < n - 1 ; ++i) {
for ( int j = 0 ; j < n - i - 1 ; ++j) {
if ( arr [j] < arr [j + 1 ]) {
swap ( arr [j], arr [j + 1 ]);
}
}
}
}
void sort_ascending ( double arr [], int n) {
for ( int i = 0 ; i < n - 1 ; ++i) {
for ( int j = 0 ; j < n - i - 1 ; ++j) {
if ( arr [j] > arr [j + 1 ]) {
swap ( arr [j], arr [j + 1 ]);
}
}
}
}
double maximize_linear_function ( double coefficients [], int n_coeffs , double variables [], int n_vars ) {
sort_descending ( coefficients , n_coeffs );
sort_ascending ( variables , n_vars );
double result = 0 ;
for ( int i = 0 ; i < n_coeffs ; ++i) {
result += coefficients [i] * variables [i];
}
return result ;
}
int main () {
double coefficients [] = { 2 , 4 , 1 , 3 };
int n_coeffs = sizeof ( coefficients ) / sizeof ( coefficients [ 0 ]);
double variables [] = { -5 , -3 , -1 , -4 };
int n_vars = sizeof ( variables ) / sizeof ( variables [ 0 ]);
double max_value = maximize_linear_function ( coefficients , n_coeffs , variables , n_vars );
cout << "Valoarea maxima a functiei liniare este: " << max_value << endl ;
return 0 ;
}
using namespace std ;
void sort_descending ( double arr [], int n) {
for ( int i = 0 ; i < n - 1 ; ++i) {
for ( int j = 0 ; j < n - i - 1 ; ++j) {
if ( arr [j] < arr [j + 1 ]) {
swap ( arr [j], arr [j + 1 ]);
}
}
}
}
void sort_ascending ( double arr [], int n) {
for ( int i = 0 ; i < n - 1 ; ++i) {
for ( int j = 0 ; j < n - i - 1 ; ++j) {
if ( arr [j] > arr [j + 1 ]) {
swap ( arr [j], arr [j + 1 ]);
}
}
}
}
double maximize_linear_function ( double coefficients [], int n_coeffs , double variables [], int n_vars ) {
sort_descending ( coefficients , n_coeffs );
sort_ascending ( variables , n_vars );
double result = 0 ;
for ( int i = 0 ; i < n_coeffs ; ++i) {
result += coefficients [i] * variables [i];
}
return result ;
}
int main () {
double coefficients [] = { 2 , 4 , 1 , 3 };
int n_coeffs = sizeof ( coefficients ) / sizeof ( coefficients [ 0 ]);
double variables [] = { -5 , -3 , -1 , -4 };
int n_vars = sizeof ( variables ) / sizeof ( variables [ 0 ]);
double max_value = maximize_linear_function ( coefficients , n_coeffs , variables , n_vars );
cout << "Valoarea maxima a functiei liniare este: " << max_value << endl ;
return 0 ;
}