infoarena

Salut,

Ma lupt cu urmatoarea problema de cateva zile si nu prea imi iese cum vreau ](*,). Ma gandeam ca poate aveti voi putina inspiratie sau imi vindeti un pont. Merci.

Dandu-se un sir a, de lungime m, sa se genereze toate sirurile b cu proprietatea 0 <= b[j] <= a[j], j = 1, m, in ordinea crescatoare a sumei elementelor.
Exemplu:

a = {2, 2, 2}	b0 = { 0, 0, 0 }
	b1 = { 1, 0, 0 }
	b3 = { 0, 1, 0 }
	b6 = { 0, 0, 1 }
	b2 = { 2, 0, 0 }
	b4 = { 1, 1, 0 }
	b5 = { 0, 2, 0 }
	b7 = { 1, 0, 1 }
	b8 = { 0, 1, 1 }
	b9 = { 0, 0, 2 }

Am reusit si sa le fac in alta ordine cu un backtracking. Apoi le-am reordonat cautand liniar sirurile de fiecare ordine, dar desigur asta nu e destul de eficient.

Am o idee care se bazeaza pe generarea consecutiva. Initial le construim pe cele de suma 1, care e doar o matrice cu 1 pe diagonala principala.
Apoi, fiecare suma S se obtine prin insumarea element cu element a unui sir de suma 1 si un sir de suma S-1. Problema e cum sa nu generam sirurile de 2 ori. Am reusit cand sirul a are aceleasi elemente ({2, 2, 2}), dar nu reusesc cand elementele sunt diferite ({2, 3, 2}).

Idei?
Pot posta ce cod am pana acum, desi nu e foarte elegant.

P.S. Nu sunt sigur daca ar trebui categorizat ca tema. Nu e pt scoala, e pt lucru  :D.

Care este ordinea de generare cand suma este aceeasi? (b-urile alea sunt sortate sau nu?)

deocamdata nu este o ordine specifica atunci cand suma este aceeasi, deci orice varianta e buna. Cu cat mai eficienta, cu atat mai bine :D.
Ordinea pe care am pus-o eu la b-uri rezulta din ideea precizata, obtinem un sir de suma S dintr-un sir de suma S-1 si un sir de suma 1. In acest fel generez mereu doar siruri valide.

Daca nu ma insel, tot timpul vor exista (a[1] + 1) * (a[2] + 1) * (a[3] + 1) *... * (a[m] + 1) solutii. (Incerci sa obtii toate combinatiile posibile). Nu exista algoritmi care au complexitatea mai buna decat Backtracking.

LE: Se pot aplica optimizari, precum cele care le-ai precizat mai sus, dar in fond tot backtracking este  :)

Mai sunt si alte restrictii si precizari?

Da, asa este, avem nevoie de toate acele solutii, insa in generarea lor trebuie sa incercam cat mai putine care sunt invalide  :D.

Prin backtracking inteleg acele metode in care incerci solutii si apoi le verifici. Ideea precizata genereaza direct solutiile bune, fara alte verificari, deci imi suna mai mult a programare dinamica. In fine, e doar terminologie. In final, da, avem nevoie de toate solutiile :D.

Nu. Problema nu e din ceva concurs, e din viata reala, deci putem fi flexibili. In final, va trebui sa compar diverse metode pentru a obtine rezultatul si vedem care e mai convenabila in ceea ce priveste timpul de executie si memoria folosita. Daca se poate si paraleliza, ar fi perfect, dar aia nu e o prioritate si ma indoiesc ca se poate :D.

Da, iei pe rand fiecare combinatie posibila de numere. Insa, pentru a afisa in ordine crescatoare dupa S si pentru a evita solutiile invalide apar niste complicatii.  :?

O metoda ar fi sa faci pentru toate S-urile un back(int k, int sum, int sum_now) (k ii pozitia curenta pentru care generezi, sum ii suma la care vrei sa se ajunga, sum_now ii suma curenta a numerelor pana la pozitia k-1, inclusiv)
De asemenea, retinerii sumei partiale pentru fiecare element ajuta pentru calcularea mai rapida. (sp[ i ] = sp[ i-1 ] + a[ i ])

pentru fiecare pozitie k va fi un for in care se testeaza elementele:


max (0, sum - sum_now - (sp[ m ] - sp[ k ]) - verifica cazul in care toate elementele de la k+1 pana la m vor fi maxime, astfel incat sa se evite problema solutiilor invalide (in care suma obinuta in back e mai mica decat ar trebui sa fie)

Nu ar trebui sa se obtina nici duplicate, nici solutii invalide cand ajungi la k maxim.  8)

Orice alta precizare poate modifica radical algoritmul, inclusiv ordinea aceea cand S-urile sunt egale. :)