problema de dinamica

[•gabor_oliviu1991]

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 

[•toni2007]

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.

[•alexandru92]

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)

[•toni2007]

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.

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)  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 !

Toni

[•alexandru92]

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 ).