h1(#Sate2). 'H.Sate2':problema/sate2

Problema cere o partitionare in $k$ subseturi a caror suma sa fie egala. Aceasta problema este NP completa. Considerand restictiile problemei, putem folosi metoda Greedy. Aceasta nu va gasi mereu rezultatul dorit, dar ne marim sansele daca rulam mai multe greedy-uri diferite si vedem daca macar una gaseste o partionare buna. O alta idee ar fi sa folosim metoda Monte Carlo, se extragem un element la intamplare din rucsacul cel mai greu si sa-l mutam in rucsacul cel mai usor, astfel incat sa nu depasim greutatea necesara fiecarui rucsac, si anume $m / k$, pana ne epuizam un numar de pasi stabilit prealabil sau am gasit o solutie.
 
Facand abstractie de la restrictiile problemei, rezolvam folosind metoda programarii dinamice pentru fiecare caz, $k = 3$: $dp[i][j][p] = 1$ sau $0$ daca putem obtine, folosind primele $i$ obiecte, o partionare astfel incat primul rucsac are greutatea $j$, al doilea greutatea $p$, iar evident al treilea va avea greutate $m - j - p$. Se procedeaza similar pentru cazul cu $k = 4$. Toate solutiile mentionate iau punctaj maxim.
 

h1(#Politie). 'I. Politie':problema/politie
Observam ca politistii vor merge intai pe toate drumurile optime (dupa enunt) dintre nodurile legate direct sau indirect doar de muchii de categorie $1$, dupa aceea doar de muchii de categorie $<= 2$, de categorie $<= 3$, etc. Impartim muchiile dupa categorie. Consideram la fiecare pas $i$, $1 <= i <= D$, ca avem nodurile grupate in componente conexe astfel incat intre orice doua noduri din cadrul aceleasi componente conexe se poate ajunge mergand numai pe muchii de categorie strict mai mica decat $i$. Uitandu-ne la muchiile de categorie $i$, este posibil ca intre unele perechi de componente conexe sa fi "aparut" una sau mai multe muchii. Politistii vor dori sa faca drumuri de la orice componenta la orice alta folosind muchiile noi (atat cat se poate), avand grija sa aleaga de fiecare data un drum cu periculozitate maxima minima. Ne imaginam un graf, privind componentele deja stabilite ca pe noduri, si ca muchii intre ele doar muchiile originale de categorie $i$. Astfel, problema se reduce la a gasi un subset de muchii cu cost maxim minim astfel incat, dupa conectarea nodurilor lor aferente, intre orice doua noduri apartinand aceleeasi componente conexe din graful imaginat sa existe un drum - adica, un "Arbore partial de cost minim":http://www.infoarena.ro/problema/apm. Sortam, deci, muchiile din categoria curenta crescator dupa periculozitate si aplicam algoritmul lui Kruskal, avand grija sa introducem intr-un vector toate periculozitatile muchiilor selectate. Procedeul se repeta pana am epuizat toate muchiile. La final sortam descrescator vectorul pe care l-am mentinut si afisam primele $P$ elemente distincte.