Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Numere2 - toate sumele posibile  (Citit de 18786 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
MacWonk
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« : Iulie 14, 2013, 21:16:41 »

Salut!
Am si eu o intrebare: cum formez toate sumele posibile cu niste numere date.
De exemplu problema "numere2":

Sa consideram un sir de n numere naturale nenule a=(a1, a2, ..., an).
Să se determine lungimea maxima a unui sir de numere naturale de forma p, p+1, p+2, ..., p+k cu proprietatea ca fiecare termen din sir se poate obtine ca suma a unor numere din sirul a. La o suma un numar din sirul a poate participa o singura data.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #1 : Iulie 15, 2013, 10:16:18 »

Programare dinamica: ceva asemanator cu problema rucsacului.   Ok
d[ i ][ s ] = 1, daca se poate forma suma s cu o submultime a primelor i elemente;
Poti sa reduci memoria folosita la O(S), iar complexitatea va fi O(N*S) unde N este numarul de elemente si S suma tuturor elementelor.

Memorat
MacWonk
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #2 : Iulie 18, 2013, 14:27:16 »

Multumesc pentru raspuns!
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines