[TEMA] Subsir suma

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

Lasand la o parte codul sunt si eu curios care e algoritmul. Daca erau doar combinatii de doua numere poate era mai simplu dar fiind si de cate trei si eventual si patru, devine chiar interesant...

x

Edited by Pollux, 24 January 2015 - 19:44.

rinser, on 24 ianuarie 2015 - 19:38, said:

atunci sa zicem ca prima cerinte e pentru perechi d enumere care impreuna dau suma asta,si apoi a doua ceritna pentru 3,4 ,5 etc...

Edited by VladBtz, 24 January 2015 - 19:44.

faci toate aranjamentele de n luate cate k posibile, si vezi care dintre ele iti da suma 13.
n este lungimea vectorului de intrare si k variaza de la 2 la lungimea vectorului de intrare.

cred ca merge asa.

Suma de subsir sau de submultime?
Cunosti metoda backtraking?

Se pot repeta numerele? În exemplul tău ai 10 + 3. Poți avea și 2 + 10 + 1 ?

VladBtz, on 24 ianuarie 2015 - 19:12, said:

Nu iti iese, pentru ca daca iti aduna in ea, suma va fi incrementata indiferent de valori. Astfel, daca ai sirul {1, 2, 3, 5, 6, 9} si ai nevoie de valoarea k=7, sa zicem, suma va deveni 1, apoi 3(1+2), apoi 8(3+5), depasind k-ul. Tu ai nevoie de combinatia 2+5.

sincer,nu cred ca cea mai optima rezolvare e cu BT

VladBtz, on 24 ianuarie 2015 - 20:27, said:

pai ti-a cerut in enunt sa fie optima?

Pai daca nu vrei Backtracking, bafta cu gasirea unei dinamici.

Intrebari importante:

• suma de subsir sau de submultime?
  
• se pot repeta numere? / Poate fi refolosit un numar din input?
  
• conteaza cata memorie e folosita?
  
• elemente negative?

13=13+0
13=12+1
13=11+1+1
13=10+2+1
13=10+1+1+1
...

Asta e cel mai general caz, pur matematic. In functie de raspunsurile la intrebarile de mai sus, poti optimiza via pruning in arborele de decizie. Deci intr-un fel, vei avea oricum backtracking, intrebarea e doar backtracking over what?

Dinamic inseamna ca tii minte subarbori (subsume) calculati anterior. Din nou, cu pruning pentru subsume > k (o suma doar creste, daca nu ai numere negative).

Tot in functie de raspunsurile la toate intrebarile de mai sus, poti apuca altfel problema, incepand de la input, nu de la output.

De aceea e important sa stim raspunsurile la toate cele 4 intrebari.

Edited by OriginalCopy, 24 January 2015 - 22:14.

O idee:
sa zicem ca in v tii minte cele n numere
declari un vector aux in care aux[i] poate fi doar 1 sau 0; generezi toate numerele binare pe n biti si retii in aux[n] bitul din pozitia n; pentru fiecare numar binar pe n biti verifici daca aux[i]==1 atunci suma+=v[i] iar daca aux[i]==0 nu adaugi la suma; apoi verifici daca suma egala cu k.

@pathfinder899
poti rescrie acele instructiuni intr-un pesudocod?

MarianG, on 25 ianuarie 2015 - 09:42, said:

/* mai intai backtracking ca sa generezi in aux numere in format binar; de exemplu pentru n=4 avem aux= 0000,0001,0010... 1111
de exemplu aux=0010 inseamna
aux[0]=0
aux[1]=0
aux[2]=1
aux[3]=0
banuiesc ca se pot genera numerele astea si fara backtracking
dupa care pentru fiecare "numar" binar facem:
*/
sum=0;
for(i=0;i<n;i++)
if(aux[i]==1)
  sum+=v[i];
if(sum == k){
for(i=0;i<n;i++)
  if(aux[i]==1)
   cout<<v[i]<<" ";
cout<<endl;
}

Crezi ca e buna ideea ?