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 un camping există k căsuțe care pot fi închiriate 365 de zile din an. Orice turist poate închiria o căsuţă pentru exact m zile consecutive din an. Campingul a adunat solicitările a n turişti pe un an întreg, cu un an înainte. Fiecare turist precizează prima zi cu care doreşte să închirieze o căsuţă (1, 2, ...). Să se determine numărul maxim de turişti care vor putea fi primiţi în camping (k<=100, m<=20, n<=1000).
Pentru a rezolva această problemă, putem crea o soluție bazată pe o metodă de programare " greedy " (alegere cea mai bună într-un moment dat), urmând pașii de mai jos:
Pseudocodul pentru soluție arată astfel:
1 . Func ț ie verifica_disponibilitate (căsuță, ziua_de_start , m):
2 . Pentru i de la ziua_de_start p â n ă la ziua_de_start + m - 1 :
3 . Dac ă ocupare [căsuță][i] == 1 :
4 . Returneaz ă False
5 . Returneaz ă True
6 . Func ț ie main ():
7 . Citi ț i k , m , n ș i solicit ă rile turi ș tilor
8 . Sorta ț i solicit ă rile dup ă ziua de î nceput
9 . ocupare = [[0] * 365 ] * k
10 . turi ș ti_accepta ț i = 0
11 . Pentru fiecare solicitare î n solicit ă rile turi ș tilor :
12 . ziua_de_start = solicitare [0]
13 . Pentru c ă su ță î n intervalul (k):
14 . Dac ă verifica_disponibilitate (căsuță, ziua_de_start , m):
15 . Actualiza ț i ocupare [căsuță] pentru zilele de la ziua_de_start la ziua_de_start + m - 1
16 . turi ș ti_accepta ț i += 1
17 . Ie ș i ț i din bucla c ă su ț elor
18 . Afi ș a ț i turi ș ti_accepta ț i

# include < iostream >
using namespace std ;
const int max_k = 100 ;
const int max_n = 1000 ;
bool verifica_disponibilitate ( int ocupare[ max_k ][ 365 ], int casuta , int ziua_de_start , int m) {
for ( int i = ziua_de_start ; i < ziua_de_start + m; i++) {
if (ocupare[ casuta ][i] == 1 ) {
return false ;
}
}
return true ;
}
int main () {
int k, m, n;
cin >> k >> m >> n;
int solicitari [ max_n ][ 2 ];
for ( int i = 0 ; i < n; i++) {
cin >> solicitari [i][ 0 ] >> solicitari [i][ 1 ];
}
int ocupare[ max_k ][ 365 ] = { 0 };
int turisti_acceptati = 0 ;
for ( int i = 0 ; i < n; i++) {
int ziua_de_start = solicitari [i][ 0 ];
int durata_inchiriere = solicitari [i][ 1 ];
for ( int casuta = 0 ; casuta < k; casuta ++) {
if ( verifica_disponibilitate (ocupare, casuta , ziua_de_start , durata_inchiriere )) {
for ( int z = ziua_de_start ; z < ziua_de_start + durata_inchiriere ; z++) {
ocupare[ casuta ][z] = 1 ;
}
turisti_acceptati ++;
break ;
}
}
}
cout << turisti_acceptati << endl ;
return 0 ;
}

Puteți folosi următoarele date de intrare pentru a testa programul:
3
5
6
1 5
6 4
12 6
17 8
23 3
28 7