Probleme Rezolvate

Sa se afiseze cel mai mic numar cu exact n divizori

Se dau doua siruri de numere x

Se dau doua siruri de caractere a si b de lungime n

Se dau n numere naturale si un numar natural s

Se da un sir de n matrice a1

Se citesc de la tastatura doua siruri de caractere s1 si s2

Manual clasa a Xi a

Tehnici de programare

Metoda programarii dinamice

Se dau n numere naturale şi un număr natural S. Să se găsească, e i dacă există, soluția de a obține numărul S ca sumă de numere naturale dintre cele n numere date.
Pentru a rezolva această problemă folosind metoda programării dinamice, vom crea o matrice dp cu dimensiunile (n + 1) x (S + 1), unde dp [i][j] va fi adevărat dacă există o submulțime a primelor i numere ale vectorului care are suma j. Vom completa matricea dp și vom verifica valoarea dp [n][S] pentru a afla dacă există o soluție.

# include < iostream >
bool isSubsetSum ( int arr [], int n, int S) {
bool dp [n + 1 ][S + 1 ];
for ( int i = 0 ; i <= n; i++) {
dp [i][ 0 ] = true ;
}
for ( int i = 1 ; i <= S; i++) {
dp [ 0 ][i] = false ;
}
for ( int i = 1 ; i <= n; i++) {
for ( int j = 1 ; j <= S; j++) {
if ( arr [i - 1 ] <= j) {
dp [i][j] = dp [i - 1 ][j] || dp [i - 1 ][j - arr [i - 1 ]];
} else {
dp [i][j] = dp [i - 1 ][j];
}
}
}
return dp [n][S];
}
int main () {
int n, S;
std :: cout << " Introduceti numarul de elemente (n): " ;
std ::cin >> n;
int arr [n];
std :: cout << " Introduceti elementele vectorului: " ;
for ( int i = 0 ; i < n; i++) {
std ::cin >> arr [i];
}
std :: cout << " Introduceti suma dorita (S): " ;
std ::cin >> S;
if ( isSubsetSum ( arr , n, S)) {
std :: cout << "Exista o submultime cu suma " << S << ".\n" ;
} else {
std :: cout << "Nu exista o submultime cu suma " << S << ".\n" ;
}
return 0 ;
}

Acest program primește numărul de elemente n, elementele vectorului și suma dorită S. Apoi, verifică dacă există o submulțime a vectorului care are suma S, folosind metoda programării dinamice. La final, programul afișează rezultatul.
E xemplu de date de intrare pentru acest program:
Introduceti numarul de elemente (n) : 5
Introduceti elementele vectorului: 3 34 4 12 5
Introduceti suma dorita (S) : 9