Problema de programare dinamica

[•Maarcell]

Cum s-ar putea de redus complexitatea algoritmului pentru aceasta problema:
http://i.imgur.com/P0eanFd.jpg

E evidenta o solutie O(3^N) si alta O(N^3*P^2), dar cea din urma necesita prea multa memorie. E posibil cumva de redus complexitatea dinamicii? Sau in acest caz e mai bine de facut optimizari pentru backtrack?

[•klamathix]

Da, limitele alea sunt date pentru meet in the middle. Iti imparti sirul in 2 jumatati aproximativ egale de N / 2. Generezi toate configuratiile din stanga, le tii intr-o structura de date utila astfel incat atunci cand generezi configuratiile din dreapta sa poti afla rapid cu cate configuratii din stanga le poti cupla incat ambele sume sa fie >= p.

Asa e 3 ^ (N / 2) * QueryTime. QueryTime-ul ala iese bine .

[•Maarcell]

Cam inteleg ceea ce ai invedere, dar nu exista oare mai multe moduri de distribuire a elementelor din aceeasi submultime astfel incat suma pentru ambele sa fie >=p? Cum tratez aceasta problema?

[•klamathix]

Pai sunt, dar le iei in considerare pe toate. Brutul e 3 ^ N, esti de acord cu asta. Eu generez toate configuratiile posibile, dar le generez independent pentru partea "stanga" si partea "dreapta" (deci 2 * 3 ^ (N / 2)). Fiecare cuplare a unei configuratii A din stanga cu o configuratie B din dreapta iti da o configuratie globala valida si unica (ceea ce se vede si din faptul ca 3 ^ (N / 2) * 3 ^ (N / 2) = 3 ^ N). Ce vei face tu e ca-ti fixezi configuratia A si vrei sa vezi rapid cate configuratii B din dreapta s-ar potrivi bine (si asta faci cu o structura de date in loc sa faci brut, care ar fi tot aia ca si brutul initial).

Sper ca e mai clar, n-am inteles foarte bine in ce-ti consta nelamurirea.

[•Maarcell]

Oh, in loc la generarea numerelor ternare, eu ma gandeam la generarea combinarilor 
Mersi, am inteles abordarea ta.