Question

Se citesc două numere naturale n şi m (n >= m), apoi se citeşte un şir de n numere întregi. Să se
determine o submulţime de m elemente din şir cu proprietatea că suma elementelor din mulţime este
maxim. De exemplu, pentru n = 6, m = 3 şi şirul de numere 5, –3, 12, 8, 1, 2, soluţia este mulţimea?
( IN PASCAL AM NEVOIE, DACA-I VORBA DE VREUN PROGRAM )

Answer 1

Răspuns:

Daca prin submultime te referi la numere nu neaparat consecutive atunci o solutie simpla ar fi:

Se sorteaza vectorul ( aici pot fi folosite multe functii, qsort, selectsort, bubblesort etc..)

Si apoi se iau cele mai mari m elemente ( ultimele m )

Sort(v) /// Se sorteaza vectorul

s = 0;

for ( i = n; i > n - m; i -- ) {

   s += v[i]

}

print(s)

Nu e un program in pascal dar cred ca il poti intelege si tu

Pentru exemplul tau, sirul sortat este

-3, 1, 2, 5, 8, 12

iar cum m = 3, vom lua ultimele 3 elemente

Pentru o solutie cu un timp liniar se pot folosi statistici de ordine ceea ce duc la o solutie in O(n)

Explicație:

Sper ca te-am ajutat