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

Se dau n paralelipipede având fiecare dimensiunile ai, bi şi ci. Să se construiască un turn de înălțime maximă prin suprapunerea acestor paralelipipede. Un paralelipiped poate fi aşezat pe orice față. Un paralelipiped poate fi aranjat peste un alt paralelipiped numai dacă fața lui nu depăşeşte fața paralelipipedului pe care este pus. Rezolvaţi problema folosind metoda backtracking şi metoda programării dinamice.

# include < iostream >
# include < cstring >
using namespace std ;
const int MAX_N = 100 ;
int n;
int paralelipiped[MAX_N][ 3 ];
int dp [MAX_N][ 3 ];
bool canPlace ( int i, int j, int k) {
return (paralelipiped[i][j] < paralelipiped[k][ 0 ] && paralelipiped[i][(j + 1 ) % 3 ] < paralelipiped[k][ 1 ]) ||
(paralelipiped[i][j] < paralelipiped[k][ 1 ] && paralelipiped[i][(j + 1 ) % 3 ] < paralelipiped[k][ 0 ]);
}
int maxHeightDP ( int idx , int face) {
if ( dp [ idx ][face] != -1 ) {
return dp [ idx ][face];
}
int maxHeight = 0 ;
for ( int i = 0 ; i < n; i++) {
if (i == idx ) continue ;
for ( int j = 0 ; j < 3 ; j++) {
if ( canPlace ( idx , face, i)) {
maxHeight = max ( maxHeight , maxHeightDP (i, j));
}
}
}
dp [ idx ][face] = maxHeight + paralelipiped[ idx ][(face + 2 ) % 3 ];
return dp [ idx ][face];
}
int main () {
cin >> n;
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < 3 ; j++) {
cin >> paralelipiped[i][j];
}
}
memset ( dp , -1 , sizeof ( dp ));
int maxTowerHeight = 0 ;
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < 3 ; j++) {
maxTowerHeight = max ( maxTowerHeight , maxHeightDP (i, j));
}
}
cout << " Inaltimea maxima (DP): " << maxTowerHeight << endl ;
return 0 ;
}
# include < iostream >
# include < cstring >
using namespace std ;
const int MAX_N = 100 ;
int n;
int paralelipiped[MAX_N][ 3 ];
bool used [MAX_N];
int maxHeight = 0 ;
bool canPlace ( int i, int j, int k) {
return (paralelipiped[i][j] < paralelipiped[k][ 0 ] && paralelipiped[i][(j + 1 ) % 3 ] < paralelipiped[k][ 1 ]) ||
(paralelipiped[i][j] < paralelipiped[k][ 1 ] && paralelipiped[i][(j + 1 ) % 3 ] < paralelipiped[k][ 0 ]);
}
void maxHeightBacktracking ( int idx , int face, int currentHeight ) {
maxHeight = max ( maxHeight , currentHeight + paralelipiped[ idx ][(face + 2 ) % 3 ]);
used [ idx ] = true ;
for ( int i = 0 ; i < n; i++) {
if ( used [i]) continue ;
for ( int j = 0 ; j < 3 ; j++) {
if ( canPlace ( idx , face, i)) {
maxHeightBacktracking (i, j, currentHeight + paralelipiped[ idx ][(face + 2 ) % 3 ]);
}
}
}
used [ idx ] = false ;
}
int main () {
cin >> n;
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < 3 ; j++) {
cin >> paralelipiped[i][j];
}
}
memset ( used , false , sizeof ( used ));
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < 3 ; j++) {
maxHeightBacktracking (i, j, 0 );
}
}
cout << " Inaltimea maxima ( Backtracking ): " << maxHeight << endl ;
return 0 ;
}

Aceste două programe rezolvă problema construirii unui turn de înălțime maximă prin suprapunerea paralelipipedelor folosind metoda backtracking și metoda programării dinamice. Ambele programe primesc ca input numărul de paralelipipede și apoi dimensiunile acestora. Programele vor returna înălțimea maximă a turnului care poate fi construit.