Probleme Rezolvate

Rezolvai problema acoperirii tablei de sah de dimensiunea nxn cu un cal care porneste din patratul de c

Rezolvai problema determinarii sumei maxime intr

Pe o tabla de sah de dimensiunea nxn un cal porneste din patratul de coordonate

Rezolvai problema gasirii unui traseu pentru a iesi din labirintul de dimensiunea nxm

Rezolvai problema plaii unei sume cu bancnote cu valori date

Rezolvai problema turistului care trebuie sa gaseasca un traseu de munte in care sa urce cat mai puin

Rezolvai problema determinarii unui subsir crescator de lungime maxima folosind metoda greedy si metoda programarii dinamice

Se dau n piese de domino

Rezolvai problema costruirii tevii de lungime l din bucai de teava de lungimi a

Se dau n paralelipipede avand fiecare dimensiunile ai

Pe o tabla de sah de dimensiunea nxn un cal porneste din patratul de coordonate

Manual clasa a Xi a

Tehnici de programare

Microproiecte

Rezolvaţi problema determinării sumei maxime într-un triunghi folosind metoda greedy şi metoda programării dinamice.

# include < iostream >
# include < cstring >
using namespace std ;
const int MAX_ROWS = 100 ;
int triangle [MAX_ROWS][MAX_ROWS];
int dp [MAX_ROWS][MAX_ROWS];
int rows ;
int max_sum_dp ( int x, int y) {
if (x == rows - 1 ) {
return triangle [x][y];
}
if ( dp [x][y] != -1 ) {
return dp [x][y];
}
int sum_left = max_sum_dp (x + 1 , y);
int sum_right = max_sum_dp (x + 1 , y + 1 );
dp [x][y] = triangle [x][y] + max ( sum_left , sum_right );
return dp [x][y];
}
int main () {
cin >> rows ;
for ( int i = 0 ; i < rows ; i++) {
for ( int j = 0 ; j <= i; j++) {
cin >> triangle [i][j];
}
}
memset ( dp , -1 , sizeof ( dp ));
cout << "Suma maxima (DP): " << max_sum_dp ( 0 , 0 ) << endl ;
return 0 ;
}
# include < iostream >
using namespace std ;
const int MAX_ROWS = 100 ;
int triangle [MAX_ROWS][MAX_ROWS];
int rows ;
int max_sum_greedy ( int x, int y) {
if (x == rows - 1 ) {
return triangle [x][y];
}
int sum_left = max_sum_greedy (x + 1 , y);
int sum_right = max_sum_greedy (x + 1 , y + 1 );
return triangle [x][y] + max ( sum_left , sum_right );
}
int main () {
cin >> rows ;
for ( int i = 0 ; i < rows ; i++) {
for ( int j = 0 ; j <= i; j++) {
cin >> triangle [i][j];
}
}
cout << "Suma maxima ( Greedy ): " << max_sum_greedy ( 0 , 0 ) << endl ;
return 0 ;
}

Ambele programe primesc ca input numărul de rânduri și apoi elementele triunghiului (înălțimile) pentru fiecare rând. Programele vor returna suma maximă pe care o poate obține turistul într-un traseu de sus în jos al triunghiului.
Rețineți că metoda greedy poate să nu ofere întotdeauna soluția optimă, deoarece alege cea mai bună opțiune locală la fiecare pas, fără a lua în considerare impactul pe termen lung al deciziei. Metoda programării dinamice garantează găsirea soluției optime, dar poate necesita mai mult timp și memorie pentru a fi executată.
E exemplu de date de intrare pentru ambele programe:
5
3
7 4
2 4 6
8 5 9 3
2 5 6 2 1