|
Titlul: Răspuns: 323 Ghiozdan Scris de: Mircea Pasoi din Februarie 19, 2007, 04:45:33 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. |