|
Titlul: subsiruri suma Scris de: bieltz vlad din Ianuarie 24, 2015, 18:55:47 se citeste un sir de n numere.sa se scrie numerele care adunate ,dau o suma egal cu nr k.
exemplu n=10 9 2 7 4 5 10 3 8 1 6 si k =13 10 +3 9+4 7+5 +1 etc... ma gandeam sa sortez crescator vectorul si apoi cu i=0,i<n-1 si j=i+1;j<n sa fac o suma care cat timpe mai mica decat k sa adune in ea....nu prea iese Titlul: Răspuns: subsiruri suma Scris de: Valeriu Motroi din Ianuarie 25, 2015, 21:23:33 Depinde de N, daca N<=20 se poate de facut cu generare de submultimi.
Titlul: Răspuns: subsiruri suma Scris de: Mihai Calancea din Ianuarie 26, 2015, 04:01:38 http://en.wikipedia.org/wiki/Subset_sum_problem.
Problema e NP-Complete pe cazul general, se presupune că nu există soluție în timp polinomial relativ la input. Deci fie ai N mic și faci ceva exponențial în N -după cum ți-a sugerat Valeriu mai sus- fie ai valorile mici și o rezolvi cu programare dinamică. Hint pentru programare dinamică: Gândește-te cum poți actualiza sumele obținute dintr-o anumită mulțime atunci când o extinzi cu un nou element. Dacă ai soluții care merg atât pentru N mare cât și pentru valori mari, probabil ceva nu e în regulă. Titlul: Răspuns: subsiruri suma Scris de: bieltz vlad din Ianuarie 27, 2015, 20:46:34 si daca numarul drebuie format doar din doua numere?
Titlul: Răspuns: subsiruri suma Scris de: Mihai Calancea din Ianuarie 27, 2015, 22:31:42 Tu ce idei ai?
|