Vom aborda problema cu ajutorul tehnicii de "Flux maxim":http://www.infoarena.ro/problema/maxflow. Astfel, construim o retea in care fiecare sistem solar $i$ are asociat nodul $i$, iar fiecare uniune comerciala $j$ nodul $N + j$. Sursa si destinatia vor fi alese convenabil astfel incat sa nu se suprapuna cu nodurile necesare. Vom trage un arc de la sursa la fiecare sistem solar $i$ printr-o muchie de capacitate $solarSystemTribute[i]$, cat si un arc de la fiecare planeta la fiecare dintre uniunile comerciale din care face parte, cu capacitate $INFINIT$. In final, tragem arcuri de la uniunea comerciala $i$ la destinatie, de capacitate $unionTribute[i]$. Ramane sa rulam algoritmul de flux pe acest graf, iar fluxul maxim rezultant reprezinta solutia problemei.

Complexitate timp: $O(N^5)$ (supraestimata).

Complexitate timp: $O(N^5)$ (daca se implementeaza cu Edmonds-Karp, mai putin daca se foloseste push-relabel).

Complexitate spatiu: $O(N^2)$.
h1(#Revolta). 'D. Revolta':problema/revolta

}
==

Rezultatul este in memo[0] dupa apelul la wtf_even_better(0).

Rezultatul este in memo[ 0 ] dupa apelul la wtf_even_better(0).

Solutia de mai sus se poate obtine aproape mecanic, fara a intelege codul initial. Tot mecanic se poate obtine si solutia iterativa, care completeaza tabloul memo[] de la stanga la dreapta in timp ce calculeaza minimul din vector. Si solutia recursiva si cea iterativa pot fi vazute ca exemple simple de programare dinamica.

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.