Probleme Rezolvate

Justificai criteriul prioritaii de alegere pentru cazul in care coeficienii sunt pozitivi si in multimea a nu exista decat numere negative

Ntr o fabrica s a automatizat procesul de producie si la sfarsitul zilei de munca

Un automobilist porneste dintr

La un cabinet medical

Refaceti programul astfel incat sa se determine valoarea minima a expresiei

Fiind data o mulime a cu n numere reale

Justificati criteriul prioritatii de alegere pentru cazul in care coeficientii sunt negativi si in mulimea a nu exista decat numere pozitive

Un turist trebuie sa strabata un traseu de munte

Ntr un camping exista k casute care pot fi inchiriate 365 de zile din an

Intr un depozit al monetariei statului sosesc n saci cu monede

Fiind date multimea de numere reale a

Manual clasa a Xi a

Tehnici de programare

Metoda greedy

Într o fabrică s a autom atizat procesul de producţie şi la sfârşitul zilei de muncă, piesele sunt adunate de roboți industriali. Fiecare robot poate strânge un anumit număr de piese. Harta halei a fost împărțită printr-un caroiaj şi poate fi reprezentată printr-o matrice (NxM) ale cărei elemente pot avea valorile: 0 (pentru locurile în care nu există maşini) şi 1 (pentru locurile în care există maşini). Roboții se deplasează în spaţiul de deasupra maşinilor, corespunzător aceluiaşi caroiaj. Roboții pornesc din colțul din stânga sus (1,1) şi trebuie să ducă piesele în colțul din dreapta jos (n,m). Roboții sunt programați astfel încât să se deplaseze doar la dreapta sau în jos. Să se scrie un program care să determine numărul minim de roboți care trebuie porniţi pentru a strânge toate piesele fabricate într-o zi.

# include <iostream>
using namespace std;
const int max_dim = 100 ;
int main () {
int n, m;
cin >> n >> m;
int harta[max_dim][max_dim];
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
cin >> harta[i][j];
}
}
int dp[max_dim][max_dim];
dp[ 0 ][ 0 ] = (harta[ 0 ][ 0 ] == 1 ) ? 0 : 1 ;
for ( int i = 1 ; i < n; i++) {
dp[i][ 0 ] = dp[i - 1 ][ 0 ] + (harta[i][ 0 ] == 1 ? 0 : 1 );
}
for ( int j = 1 ; j < m; j++) {
dp[ 0 ][j] = dp[ 0 ][j - 1 ] + (harta[ 0 ][j] == 1 ? 0 : 1 );
}
for ( int i = 1 ; i < n; i++) {
for ( int j = 1 ; j < m; j++) {
int cost = (harta[i][j] == 1 ? 0 : 1 );
dp[i][j] = min (dp[i - 1 ][j], dp[i][j - 1 ]) + cost;
}
}
cout << "Numarul minim de roboti: " << dp[n - 1 ][m - 1 ] << endl;
return 0 ;
}

Pentru a rula programul, trebuie să introduceți datele de intrare în următoarea ordine:
Un exemplu de date de intrare ar putea fi:
4 4
0 1 0 0
0 0 1 1
1 1 1 0
1 0 0 1
Programul va afișa numărul minim de roboți care trebuie porniți pentru a strânge toate piesele:
Numarul minim de roboti: 3