Titlul: Numere2 - toate sumele posibile Scris de: Mihai Alexandru Cosmin din 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. Titlul: Răspuns: Numere2 - toate sumele posibile Scris de: Pirtoaca George Sebastian din 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. Titlul: Răspuns: Numere2 - toate sumele posibile Scris de: Mihai Alexandru Cosmin din Iulie 18, 2013, 14:27:16 Multumesc pentru raspuns!
|