|
Titlul: problema de dinamica Scris de: gaboru corupt din Februarie 16, 2009, 23:47:45 se dau doua numere A si B si un vector V[] cu N elemente numere naturale. Se cere sa se ajunga printr-un numar minim de adunari sau scaderi a numerelor din V[] cu numarului A in numarul B.
Ex: A=10 B=27 si V={10,7,9,15} 27=A+15+9-7 (una dintre solutii) PS: exemplul l-am facut eu, asa ca nu stiu daka e 100% bine, dar problema asa e :peacefingers: Titlul: Răspuns: problema de dinamica Scris de: Pripoae Teodor Anton din Februarie 17, 2009, 00:24:59 O problema asemanatoare e problema pipe http://infoarena.ro/problema/pipe. Din cate imi aduc aminte, am scos 80 in concurs pe ea cu urmatoarea solutie:
Tineam numerele atat cu + cat si cu - si aplicam problema rucsacului, vazand daca pot obtine suma abs(a -b). Nu stiu cat de corect este (am avut 2 wrong answeruri, dar n-am mai avut sursa sa debugez sa vad de ce). Din ce am vazut pe sursa oficiala se incearca o dinamica C[ i ] = costul minim de a obtine i, si se cauta C[ i ] + C[i + abs(a - b) ] minim. Titlul: Răspuns: problema de dinamica Scris de: alexandru din Februarie 17, 2009, 06:37:20 Solutia corecta este 27=A+10+7. :).
Poti determina prin p dinamica suma maxima , mai mica ca B cu A. Daca is mai multe variante se selecteaza cea cu lungime minima. :). Daca nu ma insel complexitatea algortimulului este O(N); @Toni. La problema ce ai propuso, poti incerca combinatii multiple, tot pdinamic.Sau o functie de tip fill, un fel de back dar mai...usor si eficient (dar dupa dimensiuni nu ar lua punctaj maxim) :) Titlul: Răspuns: problema de dinamica Scris de: Pripoae Teodor Anton din Februarie 17, 2009, 14:00:31 Cu back nu cred ca poti obtine mai mult de 30 de puncte. Oricum aceasta nu este o rezolvare potrivita, deci nu avem de ce sa o discutam aici, ci cel mult in topicul problemei, desi mie m-i se pare inutil. Daca chiar esti sigur ca e buna solutia baga o sursa si vezi.
Citat Poti determina prin p dinamica suma maxima , mai mica ca B cu A. Daca is mai multe variante se selecteaza cea cu lungime minima. Smile. Daca nu ma insel complexitatea algortimulului este O(N); Revenind on-topic, nu vad cum scoti tu o(N), ai o(SumaNumerelor) stari si o(N) recurenta, astept sa explici smenul tau pt o(N) :eyebrow: Nu am inteles ce vrei sa spui prin combinatii multiple. Incearca sa te exprimi putin mai coerent si cu mai putine greseli de ortografie. In afara de ca ai spus solutia corecta, postul tau imi pare cam inutil, nu aduce nimic nou. Spor in rezolvare ! :P Toni Titlul: Răspuns: problema de dinamica Scris de: alexandru din Februarie 17, 2009, 15:45:26 Cand m-am referit la combinari multiple nu ma refeream la back, logic ca el e ineficinet. Ma refeream ca in loc sa generezi o singura combinatie odata , sa iei mai multe in calcul,adica toate posibilitatile (adica pe pozita i daca se potrivesc mai multe variante, sa le iei pe toate in calcul, aici te joci cu adunari si scaderi :) ).
Da, scuze am gresit complexitatea,ma gandeam la algoritmul de suma maxima. (codurile ,daca le fac, o sa fie peste aproximativ o luna, is prea ocupat acuma ). |