Răspuns: 323 Ghiozdan

[•domino]

Exista mai multe solutii care iau o groaza de punucte , desi nu ar trebui:

1. Greedy luand cea mai mare greutate, pana cand se ajunge la o greutate <= 1000. Se aplica apoi o dinamica clasica cu o matrice 200x1000 pentru reconstituire.

2. Se sorteaza greutatile descrescator si apoi se aplica un rucsac clasic (s-ar putea sa mearga chiar O(N*G)!) si se pastreaza doar un vector de predecesori pentru reconstituire.

Trebuie exemple de surse care implementeaza ideile de mai sus, cat si alte metode gresite care au luat multe puncte.