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.

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

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

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 .

Mai sunt si alte restrictii si precizari?

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 .

deocamdata nu este o ordine specifica atunci cand suma este aceeasi, deci orice varianta e buna. Cu cat mai eficienta, cu atat mai bine .
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.

[a]

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  .

oare de ce ar vrea cineva sa incrementeze numarul? asta nu e clar ca te va duce catre un numar mai mare de operatii? aveti cumva vreun contra-exemplu?

Pai eu la vectorii STL ma refer.
 Si e adevarat ca nu ai cum sa vezi toate valorile vectorului( decat primele 1000 pentru ca pana acolo te lasa textbox-ul de la count sa maresti( dar nici nu ai nevoie mai mult totusi).
-bagi V ( care l-ai declarat vector<int> V) in casuta de la watch;
-bifezi watch as array;
-prima casuta de count lasi 0;
-si la a 2-a casuta de count maresti pana la 12.
Si cu asta vei vedea elementele din vector de la 0 pana la 12.

unde bifez "watch as array"? ... sau nu te referi la MinGw? si count? nu gasesc instructiunile tale pe MinGw

legat de problema 2, cea cu submatricea de suma maxima. zice

Cel mai bun algoritm cunoscut pentru această problemă are complexitatea O(N^{3\sqrt{\frac{\log \log N}{\log N}}}) şi este mai mult un algoritm teoretic decât unul practic, uşor implementabil. Pentru detalii puteti consulta lucrarea [3].

... unde e lucrarea [3]? mi se pare ca problema urmatoare nu are legatura cu aceasta

[if]

are cineva vreo idee de ce imi intra in ciclu infinit la partea de mai jos:

Cod:

do
	{
		modif = false;
		for ( int i = 1; i <= m; ++i )
			for ( int j = 1; j <= n; ++j )
				if ( c[i][j] != CEVA_MARE )
					for ( int d = 0; d < 4; ++d )
					{
						iv = i + di[d];
						jv = j + dj[d];
						EFORT = Effort ( a[i][j], a[iv][jv] );
						if ( OK ( iv, jv ) and c[iv][jv] > c[i][j] + EFORT )
						{
							c[iv][jv] = c[i][j] + EFORT;
							modif = true;
						}
					}
	} while ( modif );

cred ca e din cauza compararii a 2a numere reale.... am urmarit executia si am vazut ca intra prin ultimul if si daca c[iv][jv] este egal cu c[j] + EFORT ... adica, EFORT nu da de fiecare data la fel pentru aceiasi 2 vecini.

stie cineva ce are testul 2 si testul 3 mai special?
iau Incorrect si imi da cu un rand mai putin (verificat).
se poate sa fie sters si ultimul sau primul rand?

in caz ca se mai uita cineva pe aici... ce e aceea parsare? si, ce are asa de special testul 4? daca mai stie cumva careva problema...
trimiteti-mi PM daca raspundeti. Multumesc

am si eu o mica intrebare la STL .... daca am o functie care vreau sa imi preia un vector<int>  ... preia singura? sau cum ar trebui sa procedez?

de ex: int F ( vector <int> p(50), vector <int> b(50) )
si mie mi se transmit catre functie doi vectori... cu pana la 50 de elemente... ii preia functia direct sau trebuie sa o fac eu manual? daca nu, cum fac treaba asta manual:D?

aha... multumesc de indicatie... il gasesc tot pe infoarena... ?

salut. mi-am instalat si eu acasa mingw, noul compilator/editor si am o mica problema: nu pot compila sau rula programele scrie. am urmat ghidul de pe site cu facerea proiectelor, a surselor, dar nu pot compila. e ca si cum nu e activat "butonu" de compilare....

are nevoie de ceva plug-in sau chestii de genu?